Linguaggi regolari
Ciao a tutti, dovrei dimostrare o confutare le seguenti definizioni:
1. Ogni sottoinsieme di un linguaggio regolare è regolare.
2. Ogni linguaggio regolare ha un proprio sottoinsieme che è anche regolare.
La 1. dovrebbe essere falsa poichè se ad esempio prendiamo il linguaggio regolare (a+b)* troviamo molti sottoinsiemi di tale linguaggio che non sono regolari. Per la 2 ho qualche dubbio, anche se credo che sia vera. Qualcuno può aiutarmi??
Grazie in anticipo
1. Ogni sottoinsieme di un linguaggio regolare è regolare.
2. Ogni linguaggio regolare ha un proprio sottoinsieme che è anche regolare.
La 1. dovrebbe essere falsa poichè se ad esempio prendiamo il linguaggio regolare (a+b)* troviamo molti sottoinsiemi di tale linguaggio che non sono regolari. Per la 2 ho qualche dubbio, anche se credo che sia vera. Qualcuno può aiutarmi??
Grazie in anticipo
Risposte
Ciao bjunior 
Partiamo dalla prima affermazione. Giusto, è falsa e si possono trovare numerosi controesempi. Nel caso specifico del tuo linguaggio però non mi sembra che esistano sottoinsiemi dello stesso che non sono regolari (sto provando ora ad occhio, magari non riesco a vederlo io ed in caso correggimi). Piuttosto un esempio semplice che mi viene in mente è questo: se consideri il linguaggio $L = \{a^{\star}b^{\star}c^{\star}\}$ ed il suo particolare sottoinsieme $L' = \{a^nb^mc^n,n, m \ge 0\}$ è facile notare come quest'ultimo non sia regolare. Difatti possiamo dire che per $L$ è possibile costruire un automa finito determinisco che lo riconosce e per $L'$ invece no (questa è una tra le condizioni necessarie e sufficienti affinché un linguaggio sia regolare). D'altra parte è anche intuitivo in un certo senso pensare che la prima affermazione sia falsa poiché un linguaggio regolare è chiuso per le operazioni di unione, intersezione e star di Kleene ma non sottoinsieme.
Veniamo alla seconda affermazione. Questa è vera ed un linguaggio regolare sottoinsieme di un altro linguaggio regolare può essere sempre banalmente trovato (è facilissimo, vediamo se ci arrivi rapidamente
).
Partiamo dalla prima affermazione. Giusto, è falsa e si possono trovare numerosi controesempi. Nel caso specifico del tuo linguaggio però non mi sembra che esistano sottoinsiemi dello stesso che non sono regolari (sto provando ora ad occhio, magari non riesco a vederlo io ed in caso correggimi). Piuttosto un esempio semplice che mi viene in mente è questo: se consideri il linguaggio $L = \{a^{\star}b^{\star}c^{\star}\}$ ed il suo particolare sottoinsieme $L' = \{a^nb^mc^n,n, m \ge 0\}$ è facile notare come quest'ultimo non sia regolare. Difatti possiamo dire che per $L$ è possibile costruire un automa finito determinisco che lo riconosce e per $L'$ invece no (questa è una tra le condizioni necessarie e sufficienti affinché un linguaggio sia regolare). D'altra parte è anche intuitivo in un certo senso pensare che la prima affermazione sia falsa poiché un linguaggio regolare è chiuso per le operazioni di unione, intersezione e star di Kleene ma non sottoinsieme.
Veniamo alla seconda affermazione. Questa è vera ed un linguaggio regolare sottoinsieme di un altro linguaggio regolare può essere sempre banalmente trovato (è facilissimo, vediamo se ci arrivi rapidamente
).
Ciao onlyReferee
Innanzitutto grazie per la risposta. Per la prima affermazione avevo trovato il linguaggio \(\displaystyle L'=(a^nb^m,n \ge m \ge 0) \), mi puoi confermare che questo non sia un sottolinguaggio regolare?
Per la seconda affermazione forse mi sto perdendo in un bicchier d'acqua ma non mi viene in mente nulla
Innanzitutto grazie per la risposta. Per la prima affermazione avevo trovato il linguaggio \(\displaystyle L'=(a^nb^m,n \ge m \ge 0) \), mi puoi confermare che questo non sia un sottolinguaggio regolare?
Per la seconda affermazione forse mi sto perdendo in un bicchier d'acqua ma non mi viene in mente nulla
Di nulla, tranquillo.
Riguardo alla prima risposta: il tuo linguaggio $L'$ è regolare in quanto puoi costruire un semplice automa deterministico a stati finiti che lo riconosce. In ogni caso il tuo $L'$ non nemmeno un sottoinsieme di $(a + b)^{\star}$. Semmai il tuo $L'$ è sottoinsieme del linguaggio $a^{\star}b^{\star}$, forse intendevi questo. Concordi
Riguardo alla seconda affermazione ti do un indizio più preciso: guarda bene la definizione ricorsiva di linguaggio regolare per determinare quel particolare linguaggio regolare di cui ti accennavo in precedenza.
Riguardo alla prima risposta: il tuo linguaggio $L'$ è regolare in quanto puoi costruire un semplice automa deterministico a stati finiti che lo riconosce. In ogni caso il tuo $L'$ non nemmeno un sottoinsieme di $(a + b)^{\star}$. Semmai il tuo $L'$ è sottoinsieme del linguaggio $a^{\star}b^{\star}$, forse intendevi questo. Concordi
Riguardo alla seconda affermazione ti do un indizio più preciso: guarda bene la definizione ricorsiva di linguaggio regolare per determinare quel particolare linguaggio regolare di cui ti accennavo in precedenza
.
Allora per la seconda ci sono arrivato in quanto un linguaggio vuoto è un linguaggio regolare.
Per la prima come mai \(\displaystyle L' \) non è un sottoinsieme di \(\displaystyle (a+b)^* \)?? \(\displaystyle (a+b)^* \) non comprende tutte le stringhe di finita lunghezza che si possono formare con \(\displaystyle a \) e \(\displaystyle b \) e quindi anche le stringhe di \(\displaystyle L' \)? Poi come faccio a rapprensentare \(\displaystyle L' \) con un automa a stati finiti dato che \(\displaystyle n \ge m \)?
Per la prima come mai \(\displaystyle L' \) non è un sottoinsieme di \(\displaystyle (a+b)^* \)?? \(\displaystyle (a+b)^* \) non comprende tutte le stringhe di finita lunghezza che si possono formare con \(\displaystyle a \) e \(\displaystyle b \) e quindi anche le stringhe di \(\displaystyle L' \)? Poi come faccio a rapprensentare \(\displaystyle L' \) con un automa a stati finiti dato che \(\displaystyle n \ge m \)?
Ciao bjunior
Sì, scusa. Sarà stata l'ora tarda in cui stavo navigando sul forum ma in effetti nella fretta non ho letto correttamente le espressioni regolari che denotano il tuo $L$ ed il tuo $L'$, sorry. Pertanto confermo che anche quanto da te detto (con il controesempio proposto) riguardo al primo punto è corretto. Il mio non è altro che un altro controesempio.
Esattamente anche per quanto riguarda il primo punto, hai colto il fatto del linguaggio vuoto.
Spero di esserti stato d'aiuto.
Sì, scusa. Sarà stata l'ora tarda in cui stavo navigando sul forum ma in effetti nella fretta non ho letto correttamente le espressioni regolari che denotano il tuo $L$ ed il tuo $L'$, sorry. Pertanto confermo che anche quanto da te detto (con il controesempio proposto) riguardo al primo punto è corretto. Il mio non è altro che un altro controesempio.
Esattamente anche per quanto riguarda il primo punto, hai colto il fatto del linguaggio vuoto.
Spero di esserti stato d'aiuto.
Si grazie mille onlyReferee mi sei stato veramente di aiuto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo