[Informatica teorica] linguaggi regolari
Ciao a tutti..sono alle prese con l'ODIATA ( perlomeno da me ) informatica teorica..
Dire che non ho dimestichezza con queste cose è poco..il corso è stato tenuto MALISSIMO, e quando mi trovo a fare gli esercizi non so dove sbattere la testa..o meglio, ho le idee, ma poi..
Una delle cose che mi blocca maggiormente è il pumping lemma e la sua applicazione..in particolare volevo proporvi un esercizio, e vedere se riuscivo un po' a chiarirmi le idee..
Sia $ L= ( w in (0,1)^** : $ numero di 1 in w è multiplo di 3, numero di 0 in w è multiplo di 2 $)$
Stabilire se tale L è regolare. In caso affermativo costruire un DFA A e formalmente dimostrare che L=L(A). In caso negativo dimostrare formalmente che L non è regolare.
Leggendo penso subito che qui o uso il pumping lemma per dimostrare la non regolarità, oppure uso l'induzione sulla lunghezza delle stringhe per dimostrare che L=L(A) dopo aver disegnato l'automa.
Ma il passo iniziale suppongo sia dare una motivazione intuitiva sul fatto che tale linguaggio sia o non sia regolare e quindi agire di conseguenza poi formalmente con la dimostrazione di una cosa o dell'altra.o sbaglio?
Come faccio a dire già da una prima occhiata se è o non è regolare?
Io direi che poichè devo tenere traccia del numero di 0 e di 1 contati il linguaggio proposto NON è regolare..andrei ad utilizzare poi il pumping lemma..ma..non sono sicura, è tutta una ipotesi, non ho un'idea di come affrontare la cosa a livello di intuizione..
Mi potete dare un suggerimento?
Grazie mille!
Dire che non ho dimestichezza con queste cose è poco..il corso è stato tenuto MALISSIMO, e quando mi trovo a fare gli esercizi non so dove sbattere la testa..o meglio, ho le idee, ma poi..
Una delle cose che mi blocca maggiormente è il pumping lemma e la sua applicazione..in particolare volevo proporvi un esercizio, e vedere se riuscivo un po' a chiarirmi le idee..
Sia $ L= ( w in (0,1)^** : $ numero di 1 in w è multiplo di 3, numero di 0 in w è multiplo di 2 $)$
Stabilire se tale L è regolare. In caso affermativo costruire un DFA A e formalmente dimostrare che L=L(A). In caso negativo dimostrare formalmente che L non è regolare.
Leggendo penso subito che qui o uso il pumping lemma per dimostrare la non regolarità, oppure uso l'induzione sulla lunghezza delle stringhe per dimostrare che L=L(A) dopo aver disegnato l'automa.
Ma il passo iniziale suppongo sia dare una motivazione intuitiva sul fatto che tale linguaggio sia o non sia regolare e quindi agire di conseguenza poi formalmente con la dimostrazione di una cosa o dell'altra.o sbaglio?
Come faccio a dire già da una prima occhiata se è o non è regolare?
Io direi che poichè devo tenere traccia del numero di 0 e di 1 contati il linguaggio proposto NON è regolare..andrei ad utilizzare poi il pumping lemma..ma..non sono sicura, è tutta una ipotesi, non ho un'idea di come affrontare la cosa a livello di intuizione..
Mi potete dare un suggerimento?
Grazie mille!
Risposte
Se avessimo avuto \( \displaystyle L_1 = \{ w \in \{0,1\}^{*} \quad | \quad \text{ il numero di 1 in }w\text{ è multiplo di 3} \}\), cosa avresti detto?
$L_1$ è regolare?
$L_1$ è regolare?
Avrei detto sempre di no, per lo stesso motivo di prima. Perchè non esiste un DFA che "conta", ho letto una cosa del genere su una dispensa da qualche parte..
Non ho proprio idea di come fare a stabilire "a naso" se un linguaggio è regolare o meno..
Una stringa che appartiene al linguaggio L da me indicato può essere $ w=0^(3k)1^(2k) $ ?
Scusate per le domande banali, magari, e anche stupide magari, ma proprio mi perdo in questa materia..
Non ho proprio idea di come fare a stabilire "a naso" se un linguaggio è regolare o meno..
Una stringa che appartiene al linguaggio L da me indicato può essere $ w=0^(3k)1^(2k) $ ?
Scusate per le domande banali, magari, e anche stupide magari, ma proprio mi perdo in questa materia..
Stai facendo un po' di confusione.
Prendiamo il mio esempio, cioè $L_1$ come definito sopra.
Questo potrebbe essere un dfa per rappresentarlo:
Prendiamo il mio esempio, cioè $L_1$ come definito sopra.
Questo potrebbe essere un dfa per rappresentarlo:
Ok, fin qui ci sono..quindi dici che dato che esiste questo DFA si deduce che L1 è regolare..giusto?
Esatto. Quindi, come vedi, in alcuni casi si può anche "contare" anche con i dfa.
Prova a fare il dfa del linguaggio $L$. Non è troppo diverso da quello che ho fatto io.
Bisogna "contare" le occorrenze, oltre che degli $1$, anche degli $0$ .
Prova a fare il dfa del linguaggio $L$. Non è troppo diverso da quello che ho fatto io.
Bisogna "contare" le occorrenze, oltre che degli $1$, anche degli $0$ .
Ora provo .. poi se ho l'illuminazione posto qui..grazie mille intanto!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo