Automi e Linguaggi Regolari
Alberto Cuesta Cañada
Introduzione
• Lo scopo della informatica e diventare
possibile la communicazione tra l’uomo e i
computer.
• Prima dobbiamo trovare un linguaggio
commune, o meggio, costruirlo.
Linguaggi
• Definizioni:
• Σ= Insieme di letteri
• X= a …a |a є Σ = parola (finita)
1
i
j
• X*=Tutte le parole generate per Σ
Linguaggi
• Un linguaggio e un insieme di parole (puo
essere infinito) da un alfabeto finito.
• Si genera con grammatiche con struttura di
frase.
Phrase Structure Grammars
• G={V, Σ, P, S}
• Grosso modo una grammatica sono lettere e
regole per costrurre parole.
• L(G) e’ il linguaggio composto per tutte le
parole generate per G.
• P=(V- Σ)+ x V*
Context Sensitive Grammars
• Le produzione hanno la forma:
• uAv→uwv dove
u,v є V * (forse λ)
A є (V- Σ)
w є V*, w≠ λ
• Lcsf=(anbncn)
Context Sensitive Grammars
• Grosso modo, un non-terminale determinato
puo essere cambiato per una cattena di
lettere determinata in un certo contesto.
Context Sensitive Grammars
• E dimostrabile che queste grammatiche
possono essere transformate in altri
equivalente:
• u→v
• A→a
u є (V- Σ)+, v є (V- Σ) *
A є (V- Σ), a є Σ
Context Free Grammars
• Le produzione hanno la forma:
• A→x
dove
x є (V) * (forse λ)
A є (V- Σ)
• Lcfg=(anbn)
Context Free Grammars
• E dimostrabile che queste grammatiche possono
essere transformate in altra equivalente del modo:
• A→xv dove
x,v є V (forse λ)
A є (V- Σ)
• Questo serve per produrre alberi binari
Context Free Grammars
• Definizione: Una parola ‘e in forma
canonica se tutte le sue derivazione sono
nell stesso senso (destra o sinistra)
• S→Sa| λ
S
S
S
S
a
a
a
Linear Context Free Grammars
• Una grammatica di cui tutte le forme
possibili sono canoniche a destra (sinistra)
se dice che e’ lineale a destra (sinistra).
• E’ dimostrabile che queste grammatiche
sono equivalenti alle grammatiche regolari.
• L=(aibj)
Grammars
Phrase Structure Grammars
Context Sensitive Grammars
Context Free Grammars
Linear Context Free Grammars
Automi
•
•
•
•
•
•
Un automa e’ una 5-tupla {Q, Σ, δ, q0, F}
Q=Stati.
1
Σ=Alfabeto.
b
a
λ
δ =Transizioni.
0
3
b
q0 =Stato Iniziale.
a
2
F=Stati Finali.
a
LCF Grammars e Automi
• E’ dimostrabile la correspondenza tra
Linguaggi Regolari e Automi Finiti.
• L=(a+b)*
λ
3
λ
0
λ
1
λ
2
λ
5
a 4
b 6
λ
λ
λ
7
λ
8 λ
9
Operazioni con Automi:
AFλ →AFN
• Si puo trovare un automa finito non
determinista per ogni automa finito con
transizioni vuoti:
λ
3
λ
0 λ 1 λ 2
λ
5
a 4
b 6
λ
λ
λ
7 λ 8 λ 9
Operazioni con Automi:
AFλ →AFN
λ
3
λ
0 λ 1 λ
2
λ
5
a 4
b 6
λ
λ
λ
7 λ 8 λ
• Prendiamo uno stato e troviamo la sua λclousure.
• 0 → 0,1,2,3,5,8,9
9
Operazioni con Automi:
AFλ →AFN
a
4
λ
0
λ
b
6
λ
• Prendiamo un altro stato diverso e ripetiamo:
• 4 → 7,0
7
a
4
Operazioni con Automi:
AFλ →AFN
b 6
a,b
6
λ
• Ripetiamo:
• 6 → 6,4
Il metodo finisce
quando non c’e’
nessuna
transizione vuota
Operazioni con Automi:
AFN →AFD
• Si puo trovare un automa finito determinista
per ogni automa finito non determinista:
a
b
1
3
a
b
0
b
2
b
a
4
5
a
Operazioni con Automi:
AFN →AFD
Stato a
b
0
1
2
1
V
3
2
1,4
V
3
V
b
1
a
a
a,b
4,5
1,4
V,5
V,3
4,5
V,5
V
V,5
V
V
V,3
V
V,4,5
V,4,5
V,5
V
V
V
V
3
b
a
b
V
4,5
a,b
0
a
b
b
V,3
2
b
a
b
b
1,4
a
a
V,4,5
a
V,5
Operazioni con Automi:
AFD →AFD Minimo
• E’ molto utile lavorare con automi minimi:
b
1
3
a
a
a,b
b
a
b
9
5
a,b
0
a
b
b
7
2
b
a
b 8
b
4
a
a
a
6
Operazioni con Automi:
AFD →AFD Minimo
5,6,8 є F → B1={1,2,3,4,7,9}, B2={5,6,8}
Stato
a
b
B1 0
B1
B1
1
B1
B1
2
B1
B1
3
B1
B2
4
B2
B1
7
B1
B2
9
B2
B1
B2 5
B2
B1
6
B1
B1
8
B2
B1
B1’={0,1,2}
B2’={3,7}
B3’={4,9}
B4’={5,8}
B5’={6}
Operazioni con Automi:
AFD →AFD Minimo
Stato
a
B1 0 B1
b
B1
1 B3
B2
2 B3
B3
3 B3
B4
7 B3
B4
4 B5
B3
9 B3
B3
5 B5
B3
8 B5
B3
6 B3
B3
B2
B3
B4
B5
B1’={0}
B2’={1}
B3’={2}
B4’={3,7}
B5’={4}
B6’={9}
B7’={5,8}
B8’={6}
Operazioni con Automi:
AFD →AFD Minimo
Blocco Stato
a
b
B1
0
B2
B3
B2
1
B6
B4
B3
2
B5
B6
B4
3
B6
B7
7
B6
B7
B5
4
B8
B4
B6
9
B6
B6
B7
5
B8
B6
8
B8
B6
6
B6
B6
B8
El algoritmo finisce qui, abbiamo
tolto due stati dell’ originale.
B6
a
a
B2
b
B1
b
a
B4
b
b
B3 a
B5 a
b
B7
a
B8
a,b
a,b
Pushdown Automata
• Un automa pushdown ha due nastri, uno
con il input, e altro che funziona come uno
stack.
a
Automa nell stato
Q
Z
• Questi automi sono correspondenti con le
Context Free Grammars.
Linear Bounded Automata
• Un Linear Bounded Automa ha un solo
nastro finito, in cui puo leggere e scrivere
a
Automa nell stato
Q
• Questi automi sono correspondenti con le
Context Sensitive Grammars.
Turing Machines
• Una Machina di Turing e’ una Linear Bounded
Machine che lavora su un nastro di input infinito.
a
Automa nell stato
Q
• Queste machine sono correspondenti con le Phrase
Structure Grammars.
Conclusione
Phrase
Structure
Grammars
Machine di
Turing
Context
Sensitive
Grammars
Linear
Bounded
Automi
Context Free
Grammars
Linear
Context Free
Grammars
Pushdown
Automi
Automi
Finiti