DFA che accetta l'insieme di tutte le stringhe in {0, 1}* che contengono esattamente 3 zeri anche non consecutivi.
DFA che accetta l'insieme delle stringhe in {0, 1}* che cominciano o finiscono (o entrambe le cose) con 01.
DFA che accetta l'insieme delle stringhe sull'alfabeto {0, 1} tali che ogni blocco di 5 simboli consecutivi contenga almeno due 0.
Ad esempio:
00011 10101è accettato10100 10110 00è accettato11011 1010non è accettato perchè nel primo blocco manca uno 0
NFA che accetta l'insieme delle parole sull’alfabeto Σ = {0, 1, 2} (per semplicità l'ho fatto solo con 0,1,2) tali che la cifra finale sia comparsa in precedenza
NFA che accetta l'insieme delle parole sull’alfabeto Σ = {0, 1, 2} (per semplicità l'ho fatto solo con 0,1,2) tali che la cifra finale NON sia comparsa in precedenza
DFA ottenuto dalla costruzione per sottoinsiemi a partire dall'NFA.
Linguaggio riconosciuto dall'automa: Stringhe in {0, 1}* che finiscono in 001 oppure 110.
DFA ottenuto con la costruzione per sottoinsiemi dall'automa:
Convertire l'automa con la seguente tabella in DFA
| a | b | |
|---|---|---|
| -> q1* | q1q2 | q3 |
| q2* | q4 | |
| q3 | q4 | |
| q4 | q1q4 |
Conversione in DFA:
Tabella delle transizioni del DFA:
| a | b | |
|---|---|---|
| -> q1* | q1q2 | q3 |
| q1q2* | q1q2 | q3q4 |
| q3 | q4 | |
| q3q4 | q4 | q1q4 |
| q1q4* | q1q2 | q1q3q4 |
| q1q3q4* | q1q2q4 | q1q3q4 |
| q1q2q4* | q1q2 | q1q3q4 |
NB: nei disegni degli esercizi la lettera ε è equivalente a λ
Automa ε-NFA che accetta tutte le parole costituite da
- zero o più 'a'
- seguite da zero o più 'b'
- seguite da zero o più 'c'
Costruzione dell'automa ε-NFA:
Calcolo ECLOSE di ogni stato dell’automa:
- ECLOSE(q0) = {q0, q1, q2}
- ECLOSE(q1) = {q1, q2}
- ECLOSE(q2) = {q2}
Conversione in DFA: (se non ci sono simboli indica l'insieme vuoto, * indica uno stato finale)
| a | b | c | |
|---|---|---|---|
| -> q0q1q2* | q0q1q2 | q1q2 | q2 |
| q1q2* | q1q2 | q2 | |
| q2* | q2 |
NB: sono state omesse le transizioni verso l'insieme vuoto.
ε-NFA che accetta insieme delle stringhe formate solo da:
01ripetuto una o più volte010ripetuto una o più volte
Ho interpretato la consegna in modo che sia permesso mescolare i due casi, ovvero 01 010 01 01 010 è accettato.
Disegno dell'automa ε-NFA:
Conversione in DFA:
Tabella delle transizioni del DFA:
| 0 | 1 | |
|---|---|---|
| -> q0 | q1 | |
| q1 | q0q2q3 | |
| q0q2q3* | q0q1q3 | |
| q0q1q3* | q1 | q0q2q3 |
Per ognuno dei seguenti linguaggi, costruire una ER sull’alfabeto Σ={a, b, c} che li rappresenti.
Punto 1: stringhe con numero pari di 'a'
Possibile soluzione: (b+c+a(b+c)*a)*
Altra soluzione equivalente: (b+c)*(a(b+c)*a(b+c)*)*
Punto 2: stringhe che contengono '4k + 1' occorrenze di 'b', per ogni k ≥ 0
Possibile soluzione: ((a+c)*b(a+c)*b(a+c)*b(a+c)*b(a+c)*)* (a+c)*b(a+c)*
Punto 3: tutte le stringhe la cui lunghezza è un multiplo di 3
Possibile soluzione: ((a+b+c)(a+b+c)(a+b+c))*
Per ognuno dei seguenti linguaggi, costruire una ER sull’alfabeto {0, 1} che li rappresenti.
Punto 1: tutte le stringhe che contengono la sottostringa 101
Possibile soluzione: (0+1)*101(0+1)*
Punto 2: tutte le stringhe che non contengono la sottostringa 101 (NB: eps = ε)
Possibile soluzione: (0+1+eps)(1+(000*))*(0+1+eps)
Sfida: tutte le stringhe che interpretate come numeri binari rappresentano un multiplo di 3.
DFA corrispondente (dal quale si può ottenere la RE):
L'automa modella i possibili resti (modulo 3) di ogni stringa binaria interpretata come numero binario. Pertanto accetta solamente se il resto è 0, cioè quando è un multiplo di 3.
Espressione regolare che accetta tutte le stringhe su Σ={a, b} che contengono esattamente 2 oppure 3 lettere 'b'
Soluzione: a*ba*ba*(ba*+a*)
Espressione regolare che accetta stringhe con numero di 0 multiplo di 5.
Soluzione: (1+(01*01*01*01*0))*