alfabeti linguaggi automi grammatiche e compilatori a cura del prof. ionta silvio a.s. 2005
TRANSCRIPT
Alfabeti Alfabeti Linguaggi Linguaggi
AutomiAutomiGrammaticGrammatic
he he e e
CompilatoriCompilatori
Alfabeti Alfabeti Linguaggi Linguaggi
AutomiAutomiGrammaticGrammatic
he he e e
CompilatoriCompilatoriA cura del A cura del
prof. Ionta Silvioprof. Ionta Silvioa.s. 2005a.s. 2005
Prof. Ionta Silvio Anno 2005 2
Mappa• Alfabeti• Linguaggi• Algebra dei Linguaggi• Automi• Operazioni sugli Automi• Esempi
AlfabetiAlfabetiAlfabetiAlfabeti
Unità didattica n° 1Unità didattica n° 1
Prof. Ionta Silvio Anno 2005 4
A ALFABETOInsieme finito di simboli
elementari
Es. :Alfabeto formato dal sol simbolo a A = {a}Alfabeto Binario A = {0,1}Alfabeto Morse A = {- , . , spazio }Alfabeto carte da gioco A = {, , , ,}Alfabeto della Lingua Italiana A = {a,b,c,…, z,A,B,C, … , Z}Alfabeto della Lingua Inglese A = {a,b,…,z,x,y,w.j,k}Alfabeto Greco A = {α,β,γ,δ,ε ,…,φ,χ,ω}
Prof. Ionta Silvio Anno 2005 5
◦ Operatore Concatenazione
Si ottiene unendo il primo simbolo seguito dal secondo simbolo
a ◦ b = abb ◦ a = ba
Non gode della proprietà commutativaa ◦ b b ◦ a
Prof. Ionta Silvio Anno 2005 6
w Parola - StringaLe parole si ottengono facendo
operazioni di concatenazione fra simboli dello stesso alfabeto
A = {a} w = aaaaaaaaaa..aaaaaaaA = {a,b} w = ababaabA = {0,1} w = 01001001 parola Binaria
Prof. Ionta Silvio Anno 2005 7
ε Stringa VuotaParola ottenuta concatenando
nessun simbolo dell’alfabetoLa lunghezza della parola vuota è
|ε| = 0
Prof. Ionta Silvio Anno 2005 8
|W| Lunghezza di una Parola
È il numero di caratteri utilizzati concatenando fra loro i simboli dell’alfabeto nel formare la parola
Parola formata da 0 lettere dell’Alfabeto Greco A = {α,β,γ,δ,ε ,…,φ,χ,ω}
|w| = | ε | = 0
Parola formata da 1 lettera dell’ Alfabeto della Lingua Inglese A = {a,b,…,z,x,y,w.j,k} |w| = |x| = 1
Parola formata da 2 lettere di A = {0,1} |w| = |01| = 2
Parola formata da 3 lettere di A = {a,b} |w| = |aba| = 3
Parola formata da 4 lettere di A = {a} |w| = |aaaa| = 4
Prof. Ionta Silvio Anno 2005 9
An Potenza di un Alfabeto
Insieme delle parole che si possono formare concatenando fra loro simboli dell’alfabeto di lunghezza pari a n
Es. Alfabeto iniziale A = {a}
A0 = {ε} -> Insieme delle parole di lunghezza 0 -> la parola di lunghezza 0 è solo ε
A1 = {a} -> Insieme delle parole di lunghezza 1 la parola di lunghezza 1 è solo quella formata da un solo carattere
A2 = {aa} -> Insieme delle parole di lunghezza 2 la parola di lunghezza 2 è solo quella formata dalla concatenazione dello stesso carattere a per due volte
…An = {aaa…aaa} -> Insieme delle parole di lunghezza n la parola di
lunghezza n è solo quella formata dalla concatenazione dello stesso carattere a per n volte
Prof. Ionta Silvio Anno 2005 10
An Potenza di un AlfabetoEs. Alfabeto iniziale A = {a,b}
A0 = {ε} -> Insieme delle parole di lunghezza 0 la parola di lunghezza 0 è solo ε
A1 = {a,b} -> Insieme delle parole di lunghezza 1 la parola di lunghezza 1 è solo quella formata da un solo carattere ci sono due parole : la parola a e la parola b
A2 = {aa,ab,ba,bb} -> Insieme delle parole di lunghezza 2 la parola di lunghezza 2 è solo quella formata dalla concatenazione dei due caratteri a e b sono tante quante le combinazioni a due a due dei due caratteri = 22 = 4
A3 = {aaa,aab,aba,abb,baa,bab,bba,bbb} -> Insieme delle parole di lunghezza 2 la parola di lunghezza 2 è solo quella formata dalla concatenazione dei due caratteri a e b sono tante quante le combinazioni due a due dei due caratteri = 238
….An = {aaa…aaa,…,bbb…bbb} -> Insieme delle parole di lunghezza n la
parola di lunghezza n è solo quella formata dalla concatenazione dei due caratteri a e b sono tante quante le combinazioni n a n dei due caratteri = 2n…
Prof. Ionta Silvio Anno 2005 11
A+ Chiusura Positiva di un Alfabeto
È l’insieme di tutte le parole, non nulle e lunghezza finita, che si possono formare unendo i caratteri dell’alfabeto
A+ = A1 A2 A3 … An
w A+ |w| > 0
Prof. Ionta Silvio Anno 2005 12
A+ Chiusura Positiva di un Alfabeto
Alfabeto iniziale A = {a}
A+ = {a,aa, aaa,…,aaa..aa} 1 2 3 n
Alfabeto iniziale A = {a,b}
A+ = {a,b,aa,ab,ba,bb, aaa,aab,aba,abb,baa,bab,bba,bbb,
1 2 3
…,aaa..aa,… ,bbb…bbb} n
Prof. Ionta Silvio Anno 2005 13
A* Chiusuradi un Alfabeto
È l’insieme di tutte le parole, anche nulle e di lunghezza finita, che si possono formare unendo i caratteri dell’alfabeto
A* = A0 A1 A2 … An
w A+ |w| 0A* = A0 A+ = {ε} A+
Prof. Ionta Silvio Anno 2005 14
A* Chiusuradi un Alfabeto
Alfabeto iniziale A = {a}
A* = {ε , a, aa, aaa, …, aaa..aa} 0 1 2 3 n
Alfabeto iniziale A = {a,b} A* = { ε , a,b, aa,ab,ba,bb,
aaa,aab,aba,abb,baa,bab,bba,bbb, 0 1 2 3
…, aaa..aa,… ,bbb…bbb} n
LinguaggiLinguaggiLinguaggiLinguaggiUnità didattica n° 2Unità didattica n° 2
Prof. Ionta Silvio Anno 2005 16
L Linguaggio sull’alfabeto A
È un sottoinsieme di A* È l’insieme delle parole, di lunghezza finita anche
nulla, che si possono formare a partire dai caratteri dell’alfabeto concatenandoli fra loro e che soddisfa un particolare insieme di REGOLE
Es. il linguaggio Italiano è l’insieme di parole che si possono formare a partire dall’alfabeto Italiano e che soddisfano le regole della grammatica (sintassi) Italiana
Nota : Il linguaggio Italiano si può formare anche dall’alfabeto Inglese basta che soddisfi le regole della grammatica Italiana
Prof. Ionta Silvio Anno 2005 17
L Linguaggio sull’alfabeto AAlfabeto iniziale A = {a}
L = { w A* |w| A* } = Linguaggio formato da nessuna Parola
L = { w A* |w| = 0 } = {ε} Linguaggio formato dalla Parola Vuota parola di lunghezza zero
L = { w A* |w| = 1 } = {a} Linguaggio formato dalla Parola di lunghezza 1
Prof. Ionta Silvio Anno 2005 18
L Linguaggio sull’alfabeto A
Alfabeto iniziale A = {a}
L = { w A* a2n+1 n0 } = {a,aaa,aaaaa,…}
Linguaggio formato dalle parole con un numero dl lettere a dispari
L = {wA* a2n n>0 }={aa,aaaa,aaaaa,…}
Linguaggio formato dalle parole con un numero dl lettere a pari
Prof. Ionta Silvio Anno 2005 19
L Linguaggio sull’alfabeto A
L = { w A* R(w)= Vero }
Metodo DISCORSIVOL = insieme delle Parole formate con lettere dell’alfabeto
A, di lunghezza anche nulla ma finita, che soddisfano la particolare Regola R
Metodo ENUMERATIVO L = { elenco completo delle parole }
Metodo MATEMATICOL = formula matematica sui linguaggi
Prof. Ionta Silvio Anno 2005 20
L Linguaggio sull’alfabeto A
Es : L = {w{0,1}* Inizi con zero}
Metodo DISCORSIVOL = Insieme delle Parole formate con lettere dell’alfabeto A cioè I numeri
0 e 1, che soddisfano la particolare Regola che la parola inizi con il numero 0 che può essere seguito da una qualsiasi combinazione, anche nulla, di 0 e 1 a piacere di lunghezza finita
Metodo ENUMERATIVO L = { 0, 00, 01, 000, 001, 010, 011, 0000, 0001, 0010, 0011,…. } 1 2 3 4
Metodo MATEMATICO
L = 0(0+1)*
Algebra dei LinguaggiAlgebra dei LinguaggiAlgebra dei LinguaggiAlgebra dei LinguaggiUnità didattica n° 3Unità didattica n° 3
Prof. Ionta Silvio Anno 2005 22
Algebra dei LinguaggiA = {a,b}
Alfabeto formato da 2 simboli (caratteri)
ε Parola vuota formata non prendendo nessun carattere dell’alfabeto
a parola di lunghezza 1 formata dal 1° carattere dell’alfabeto
b parola di lunghezza 1 formata dal 2° carattere dell’alfabeto
Prof. Ionta Silvio Anno 2005 23
Algebra dei Linguaggiaa, ab,ba, bb
parole di lunghezza 2 formate concatenando due caratteri dell’alfabeto
aaa, aab,aba, abb, baa, bab, bba, bbb
parole di lunghezza 3 formate concatenando tre caratteri dell’alfabeto
Prof. Ionta Silvio Anno 2005 24
Algebra dei Linguaggi
( a + b ) Unioneab
Posso prendere 1 solo carattere a scelta fra “a” e “b”
(a◦b) (ab) Congiunzione
ab devo prendere obbligatoriamente entrambi i caratteri nello stesso ordine in cui sono indicati ( prima la “a” e poi la “b”
Prof. Ionta Silvio Anno 2005 25
Algebra dei Linguaggi
(..)+ Chiusura Positiva(..)(..)(..)(..)(..)(..)(..)(..)(..)(..). . . . .
Sequenza non vuota di (..)Posso prendere i caratteri in ripetizione in un numero qualsiasi ma obbligatoriamente almeno 1
o prendo un solo carattere (..) o posso prendo una sequenza di caratteri (..) lunga a piacere
Prof. Ionta Silvio Anno 2005 26
Algebra dei Linguaggi
(..)* Chiusura – Operatore stella
ε(..)(..)(..)(..)(..)(..)(..)(..)(..)(..)…
Sequenza anche vuota di (..)
Posso prendere i caratteri in ripetizione in un numero qualsiasi anche nessuno
o non prendo nessun (..) o posso prendo una sequenza di caratteri (..) lunga a piacere
Prof. Ionta Silvio Anno 2005 27
Algebra dei Linguaggi
a+ Chiusura Positiva
aaaaaaaaaa. . . . .
Sequenza non vuota di caratteri “a”
Posso prendere i caratteri in ripetizione in un numero qualsiasi ma obbligatoriamente almeno 1
o prendo un solo carattere “a” o posso prendo una sequenza di caratteri “a” lunga a piacere
Prof. Ionta Silvio Anno 2005 28
Algebra dei Linguaggi
a* Chiusura – Operatore stella
εaaaaaaaaaa. . . . .
Sequenza anche vuota di caratteri “a”
Posso prendere i caratteri in ripetizione in un numero qualsiasi anche nessuno
o non prendo nessun carattere “a” o posso prendo una sequenza di caratteri “a” lunga a piacere
Prof. Ionta Silvio Anno 2005 29
Algebra dei Linguaggi
(a+b)+ Chiusura Positivaa,baa,ab,ba,bbaaa,aab,aba,abb,baa,bab,bba,bbbaaaa,……
Sequenza di combinazioni non vuota di caratteri
“a” e “b”Posso prendere i caratteri in ripetizione in un numero qualsiasi scegliendoli a piacere ma obbligatoriamente almeno 1
o prendo un solo carattere “a” o un solo caratere “b” o posso prendo una sequenza di caratteri lunga a piacere
Prof. Ionta Silvio Anno 2005 30
Algebra dei Linguaggi
(ab)+ Chiusura Positivaabababababab…
Sequenza di combinazioni non vuota di coppie di caratteri
“ab”Posso prendere i caratteri in coppia in ripetizione in un numero qualsiasi ma obbligatoriamente almeno 1 coppia
o prendo una sola coppia di caratteri “ab” o posso prendo una sequenza di caratteri “ab” lunga a piacere
Prof. Ionta Silvio Anno 2005 31
Algebra dei Linguaggi
(a+b)* Chiusura – operatore Stella
ε a,baa,ab,ba,bbaaa,aab,aba,abb,baa,bab,bba,bbbaaaa,……
Sequenza di combinazioni anche vuota di caratteri
“a” e “b”Posso prendere i caratteri in ripetizione in un numero qualsiasi, anche nessuno, scegliendoli a piacereo nessuno o prendo un solo carattere “a” o un solo caratere “b” o posso prendo una sequenza di caratteri lunga a piacere
Prof. Ionta Silvio Anno 2005 32
Algebra dei Linguaggi
(ab)* Chiusura – operatore Stellaε abababababab…
Sequenza di combinazioni non vuota di coppie di caratteri
“ab”Posso prendere i caratteri in coppia in ripetizione in un numero qualsiasi , anche nessunoo nessuno o prendo una sola coppia di caratteri “ab” o posso prendo una sequenza di caratteri “ab” lunga a piacere
Prof. Ionta Silvio Anno 2005 33
Esempi di LinguaggioAlfabeto iniziale A = {a.b}
Metodo MATEMATICO ab*aMetodo DISCORSIVO L = { w A* (tutte le parole formate da lettere dell’alfabeto di partenza
“a” e “b”) t.c. |w| 2 (tali che siano formate da almeno 2 caratteri) e che iniziano e terminano con “a” con interposto una sequenza anche vuota di “b”}
Metodo ENUMERATIVO L = { aa, aba, abba, abbba, abbbba, abbbbba, … } 2 3 4 5 6 7
Prof. Ionta Silvio Anno 2005 34
Esempi di LinguaggioAlfabeto iniziale A = {a.b}
Metodo MATEMATICO a(a+b)+aMetodo DISCORSIVO L = { w A* (tutte le parole formate da lettere dell’alfabeto di partenza
“a” e “b”) t.c. |w| 3 (tali che siano formate da almeno 2 caratteri) e che iniziano e terminano con “a” con interposto una sequenza non vuota di caratteri a scelta fra “a” e “b”}
Metodo ENUMERATIVO L = { aaa, aba, aaaa, aaba, abaa, abba, aaaaa, aaaba, aabaa,
aabba, … } 3 4 5
Prof. Ionta Silvio Anno 2005 35
Esempi di LinguaggioAlfabeto iniziale A = {a.b}
Metodo MATEMATICO a(ab)*aMetodo DISCORSIVO L = { w A* t.c. |w| 2 e che iniziano e terminano con
“a” con interposto una sequenza anche vuota di coppie di caratteri a scelta “ab”}
Metodo ENUMERATIVO L = { aa, aaba, aababa,aabababa, … } 2 4 6 8
Prof. Ionta Silvio Anno 2005 36
Esempi di LinguaggioAlfabeto iniziale A = {0,1}
Metodo MATEMATICO 0(0+1)*
Metodo DISCORSIVO L = { w A* t.c. |w| 1 e che iniziano con “0” seguito da
una sequenza anche vuota di caratteri a scelta “0”e “1”}
Metodo ENUMERATIVO L =
{0,00,01,000,001,010,011,0000,0001,0010,0011,0100,0101,0110,0111, … }
1 2 3 4 >5
AutomiAutomiAutomiAutomi
Unità didattica n° 4Unità didattica n° 4
Prof. Ionta Silvio Anno 2005 38
a AutomaUn Automa riconoscitore di un Linguaggio è
una Macchina che ogni volta che si inserisce una parola del linguaggio partendo da uno Stato Iniziale qi e passando, attraverso opportune regole, in un insieme finito di Stati Intermedi qn ogni volta che legge un carattere della parola riesce a raggiungere uno degli Stati Finali qf
Prof. Ionta Silvio Anno 2005 39
a Automi
a = < A, Q, , qi = q0, F > (quintupla)
A Alfabeto di PartenzaQ Insieme degli Stati
{q0, q1, q2 , q3 , …, qf1, qf2,… ,} Regole di Transizione (Produzioni)qi Stato Iniziale q0
F Insieme degli Stati Finali { qf1, qf2,…}
Prof. Ionta Silvio Anno 2005 40
a Automi• Automa Deterministico
– Quando le regole permettono la transizione da uno Stato ad un altro in modo univoco
• Automa Deterministico– Quando le regole non permettono di
stabilire con esattezza in quale stato porterà la Transizione
Prof. Ionta Silvio Anno 2005 41
Si parte dallo stato iniziale e utilizzando la tabella di transizione si costruisce un automa equivalente ma deterministico.
Gli stati non determinati si raggruppano in un unico nuovo stato.
Pertanto le transazioni vanno effettuate considerando gli stati come se fossero raggruppati
I nuovi stati che contengono stati finali diventano stati finaliInfine si rinominano gli stati
Automa Deterministico
Automa non Deterministico
Prof. Ionta Silvio Anno 2005 42
Automa che riconosce il Linguaggio L = a
a = <A={a} , Q ={q0,q1}, , qi = q0, F={q1}
>
q0q1
Stato Iniziale
Stato Finale
a a
q0 q1
q1 -
Prof. Ionta Silvio Anno 2005 43
Automa che riconosce il Linguaggio L = b
a = <A={b} , Q ={q0,q1}, , qi = q0, F={q1}
>
q0q1
Stato Iniziale
Stato Finale
b b
q0 q1
q1 -
Operazioni sugli Operazioni sugli AutomiAutomi
Operazioni sugli Operazioni sugli AutomiAutomi
Unità didattica n° 5Unità didattica n° 5
Prof. Ionta Silvio Anno 2005 45
Unione fra automiSi crea un nuovo Stato Iniziale.Da esso si fanno uscire tante frecce
quante sono quelle che uscivano dagli stati iniziali degli altri automi e che vanno finire negli stessi stati
Gli stati Iniziali Vecchi e le frecce ad esso collegate spariscono
Prof. Ionta Silvio Anno 2005 46
Unione fra automiL = a + b Unione degli Automi L1=a e
L2=b
q1q0
a
q1q0
b
Nuovo Stato
Iniziale
q0
b
a
q2
a b
q0
q1 q2
q1
- -
q2
- -
Prof. Ionta Silvio Anno 2005 47
Concatenazione fra automi
Si scrive il 1° automa senza l’indicazione degli stati finali
Si sovrappone lo stato iniziale ad ogni stato finale del primo Automa e si costruisce da questi stati (ex finali) il 2° automa
Da essi si fanno uscire tante frecce quante sono quelle che uscivano dallo stato iniziale del 2°automa e che vanno finire negli stessi stati del 2° automa
Prof. Ionta Silvio Anno 2005 48
Unione fra automiL = ab Concatenazione degli Automi L1=a e L2=b
q1q0
a
q1q0
a
q1q0
b
q2q1
b
a b
q0
q1 -
q1
- q2
q2
- -
Prof. Ionta Silvio Anno 2005 49
Unione fra automiL = ba Concatenazione degli Automi L1=b e L2=a
q1q0
b
q1q0
b
q1q0
a
q2q1
a
a b
q0
- q1
q1
q2 -
q2
- -
Prof. Ionta Silvio Anno 2005 50
Chiusura positivaDa ogni Stato Finale dell’Automa si
fanno uscire tante frecce quante sono quelle che escono dallo Stato Iniziale che vanno a finire sempre negli stessi Stati
Prof. Ionta Silvio Anno 2005 51
Chiusura positivaL = a+ Chiusura positiva di L1= a
q1q0
aa
a
a
q0 q1
q1 q1
Prof. Ionta Silvio Anno 2005 52
Chiusura positivaL = b+ Chiusura positiva di L1= b
q1q0
bb
b
b
q0 q1
q1 q1
Prof. Ionta Silvio Anno 2005 53
Chiusura positivaL = (a + b)+ Chiusura positiva di L = a+b
q1
q0
b
a
q2
a
b
b aa
b
a b
q0
q1 q2
q1
q1 q2
q2
q1 q2
b
a
Prof. Ionta Silvio Anno 2005 54
Chiusura positivaL = (ab)+ Chiusura positiva di L = ab
q1q0
aq2q1
ba
a
a b
q0
q1 -
q1
- q2
q2
q1 -
Prof. Ionta Silvio Anno 2005 55
Chiusura positivaL = (ba)+ Chiusura positiva di L = ba
q1q0
bq2q1
ab
a
a b
q0
- q1
q1
q2 -
q2
- q1
Prof. Ionta Silvio Anno 2005 56
Operazione Stella• Si effettua la Chiusura Positiva
– Da ogni Stato Finale dell’Automa si fanno uscire tante frecce quante sono quelle che escono dallo Stato Iniziale che vanno a finire sempre negli stessi Stati
• Lo Stato Iniziale diventa Stato Finale
Prof. Ionta Silvio Anno 2005 57
Operazione StellaL = a* Operazione Stella di L1= a
q1q0
aa
a
q1q0
a
q0 q1
q1 q1
Prof. Ionta Silvio Anno 2005 58
Operazione StellaL = b* Operazione Stella di L1= b
q1q0
bb
b
q1q0
b
q0 q1
q1 q1
Prof. Ionta Silvio Anno 2005 59
Operazione StellaL = (a + b)+ Operazione Stella di L = a+b
q1
q0
b
a
q2
a
b
b aa
b
a b
q0
q1 q2
q1
q1 q2
q2
q1 q2
b
aq0
Prof. Ionta Silvio Anno 2005 60
Operazione StellaL = (ab)* Operazione Stella di L = ab
q1q0
aq2q1
ba
a
q0
a b
q0
q1 -
q1
- q2
q2
q1 -
Prof. Ionta Silvio Anno 2005 61
Operazione StellaL = (ba)* Operazione Stella di L = ba
q1q0
bq2q1
ab
b
q0
a b
q0
- q1
q1
q2 -
q2
- q1
GrammaticaGrammaticaGrammaticaGrammaticaUnità didattica n° 6Unità didattica n° 6
EsempiEsempiEsempiEsempiUnità didattica n° 7Unità didattica n° 7
Prof. Ionta Silvio Anno 2005 64
Esempio n°1 L = 0(0+1)*11
L1= 0q0
q1
0
q0q1
1L2= 1
L3= 11
1q0
q2q1
1
q1
q0
1
0
q2
0
1
1 0
L4= 0 + 1
L5= (0 + 1)*q1
1
0
q2
0
1
1 0q0
L6= 0 (0 + 1)* 0q2
1
0
q3
1
1 0q1q0
1
Lf= 0 (0 + 1)*11
q5
q3
q2
1q1q0 q4
00
1 0
0
1
1
1
1
1
Prof. Ionta Silvio Anno 2005 65
Esempio n°1 L = 0(0+1)*11
0 1
q0 q1 -
q1 q2 q3,q4
q2 q2 q3,q4
q3 q2 q3,q4
q4 - q5
q5 - -
Automa non Deterministico
Ci sono dei passaggi di stato non definiti univocamente
Es : se mi trovo nello stato q3 e leggo il carattere 1 in quale stato devo andare?
Ancora nello Stato q3 o vado nello stato q4 ?
Lf= 0 (0 + 1)*11
q5
q3
q2
1q1q0 q4
00
1 0
0
1
1
1
1
1
Prof. Ionta Silvio Anno 2005 66
Esempio n°1 L =
0(0+1)*11
0 1
q0 q1 -
q1 q2 q3,q4
q2 q2 q3,q4
q3 q2 q3,q4
q4 - q5
q5 - -
Si parte dallo stato iniziale e utilizzando la tabella di transizione si costruisce un automa equivalente ma deterministico.Gli stati non determinati si raggruppano in un unico nuovo stato.Pertanto le transazioni vanno effettuate considerando gli stati come se fossero raggruppatiI nuovi stati che contengono stati finali diventano stati finaliInfine si rinominano gli stati
Automa Deterministico
Automa non Deterministico
q0 q1
0q2
0
0
q3,q4
1 1
q3,q4,q5
1
0
0
1
0 1
q0 q1 -
q1 q2 q3,q4
q2 q2 q3,q4
q3,q4 q2 q3,q4,q5
q3,q4,q
5
- q3,q4,q5
Prof. Ionta Silvio Anno 2005 67
Esempio n°1 L = 0(0+1)*11
Automa Deterministico 0 1
q0 q1 -
q1 q2 q3
q2 q2 q3
q3 q2 q4
q4 - q4
q0 q1
0q2
00
q3
1 1
q4
10
0
1