Alfabeti Linguaggi Automi Grammatiche e Compilatori A cura del prof. Ionta Silvio a.s. 2005.

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


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 = {α,β,γ,δ,ε ,…,φ,χ,ω}


◦ 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


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


ε Stringa VuotaParola ottenuta concatenando

nessun simbolo dell’alfabetoLa lunghezza della parola vuota è

|ε| = 0


|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


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


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…


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


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


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+


A* Chiusuradi un Alfabeto


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


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


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




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



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



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


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


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


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”



(..)+ 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



(..)* 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



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



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



(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



(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



(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



(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


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



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



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


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



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


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,…}


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


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


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 -


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



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


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

- -


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


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

- -


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

- -


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


Chiusura positivaL = a+ Chiusura positiva di L1= a

q1q0

aa

a

a

q0 q1

q1 q1


Chiusura positivaL = b+ Chiusura positiva di L1= b

q1q0

bb

b

b

q0 q1

q1 q1


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


Chiusura positivaL = (ab)+ Chiusura positiva di L = ab

q1q0

aq2q1

ba

a

a b

q0

q1 -

q1

- q2

q2

q1 -


Chiusura positivaL = (ba)+ Chiusura positiva di L = ba

q1q0

bq2q1

ab

a

a b

q0

- q1

q1

q2 -

q2

- q1


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


Operazione StellaL = a* Operazione Stella di L1= a

q1q0

aa

a

q1q0

a

q0 q1

q1 q1


Operazione StellaL = b* Operazione Stella di L1= b

q1q0

bb

b

q1q0

b

q0 q1

q1 q1


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


Operazione StellaL = (ab)* Operazione Stella di L = ab

q1q0

aq2q1

ba

a

q0

a b

q0

q1 -

q1

- q2

q2

q1 -


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


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


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 - -


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


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


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


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

Alfabeti Linguaggi Automi Grammatiche e Compilatori A cura del prof. Ionta Silvio a.s. 2005.

Documents

Transcript of Alfabeti Linguaggi Automi Grammatiche e Compilatori A cura del prof. Ionta Silvio a.s. 2005.