Analisi Lessicale:
Linguaggi Regolari
Nicola Fanizzi
Corso di Linguaggi di Programmazione - 010194
Dipartimento di Informatica
Università degli Studi di Bari
18 marzo 2015
Sommario
1
Introduzione
Token
2
Espressioni Regolari
Linguaggi Formali e Operazioni
3
Automi a Stati Finiti
Automi Non-Deterministici
Automi Deterministici
-chiusura
4
Corrispondenze
Corrispondenza Automi-ER
Grammatiche Regolari
5
Minimizzazione
Indistinguibilità
Tabella a Scala
6
Pumping Lemma – linguaggi regolari
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
2 / 70
Introduzione
trasformazione stringa di caratteri in lista di token
Come si implementa?
Teoria del ling. formali
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
3 / 70
Introduzione [. . . cont.]
Scopo:
riconoscere nella stringa in ingresso
gruppi di caratteri che corrispondono a categorie
sintattiche
trasformare la stringa di caratteri in sequenze di simboli astratti
– token – da passare all’analisi sintattica
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
4 / 70
Introduzione [. . . cont.]
separazione tra analisi lessicale e sintattica
motivi teorici?
motivi pratici?
tecnologie più efficienti
maggiore semplificazione della specifica e struttura del
compilatore
semplicità nella descrizione del linguaggio
(prog. macchina astratta / programmazione)
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
5 / 70
Token
Token rappresentazione astratta di una sottostringa in ingresso
hnome, valorei
nome simbolo astratto che rappresenta una categoria sintattica
es.: identificatore, operatore, parola chiave, . . .
valore la stringa letta in ingresso
Osservazione il valore può essere sottinteso quando la
relazione nome-valore è 1-a-1 (es. parole chiave)
Esempio
token hIDE, x1i
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
6 / 70
Token [. . . cont.]
La specifica lessicale di un linguaggio è la descrizione dei suoi
token attraverso pattern che identificano la forma dei suoi
lessemi:
pattern descrizione generale della forma dei valori del token
(cfr. espressioni regolari)
lessema la stringa istanza del pattern
Esempio
N. Fanizzi ( LdP)
pattern: (x|y)(x|y|0|1)∗
Analisi Lessicale: Linguaggi Regolari
lessema: x1
18 marzo 2015
7 / 70
Token [. . . cont.]
Esempio
Nella stringa in C:
if (x > 0) printf("positivo");
potrebbero essere riconosciuti i token:
hIFi,
hIDE, printi,
h(i,
h(i,
hIDE, xi,
hCONSTSTR, positivoi,
hOPREL, >i,
h)i,
hCONSTNUM, 0i,
h;i.
h)i,
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
8 / 70
Stringhe e Operazioni
Un alfabeto è un insieme di simboli finito e non vuoto di
simboli
Esempi
Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
alfabeto delle cifre decimali
0
Σ = {a, b, c, . . . , z}
alfabeto delle lettere (minuscole)
Una stringa (o parola, word) w su un alfabeto Σ
è una sequenza finita di simboli s1 s2 · · · sn tale che
∀i ∈ {1, . . . , n} : si ∈ Σ.
La lunghezza di w è pari ad n e si denota con |w|
Esempi Alcune stringhe su Σ0 sono aaba, aca, cbaa, b, . . .
Dato Σ = {0, 1} sia w = 0010110 con |w| = 7
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
9 / 70
Stringhe e Operazioni [. . . cont.]
La stringa vuota, denotata con ,
è la parola priva di simboli (|| = 0)
Si denota con Σ∗ l’insieme di tutte le stringhe su Σ.
Osservazione ∀Σ : ∈ Σ∗
Esempio Dato Σ = {0, 1} risulta
Σ∗ = {, 0, 1, 00, 01, 10, 11, 000, 001, . . .}
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
10 / 70
Stringhe e Operazioni [. . . cont.]
Date w, z ∈ Σ∗ ,
si definisce l’operazione di concatenazione:
w·z
Osservazioni
· non commutativa
elemento neutro: w · = · w = w
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
11 / 70
Stringhe e Operazioni [. . . cont.]
Iterando, si ottiene una forma esponenziale
Data w ∈ Σ∗ , potenza k-esima di w:
k
w =
N. Fanizzi ( LdP)
k=0
k−1
ww
k>0
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
12 / 70
Linguaggi Formali
Definizione
Un linguaggio L su un alfabeto Σ è un sottoinsieme di Σ∗ :
L ⊆ Σ∗
Osservazioni
∅, {} e Σ sono linguaggi su Σ
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
(|∅| = 0 6= 1 = |{}|)
18 marzo 2015
13 / 70
Linguaggi Formali [. . . cont.]
Esempi
Linguaggio finito L = {, aab, aaaabb}.
Linguaggio infinito L = {ai b2i | i ≥ 0}.
Linguaggio delle parentesi bilanciate L ⊆ {(, )}∗ :
(())() ∈ L e ()(()()) ∈ L
mentre
(()() 6∈ L e ())(() 6∈ L
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
14 / 70
Linguaggi Formali [. . . cont.]
Dati due linguaggi L e L0 definiti sullo stesso alfabeto Σ:
prodotto L · L0 = {w = w1 · w2 ∈ Σ∗ | w1 ∈ L ∧ w2 ∈ L0 }
unione L ∪ L0 = {w ∈ Σ∗ | w ∈ L ∨ w ∈ L0 }
{}
se k = 0
k
chiusura L =
k−1
L
· L se k > 0
[
L+ =
Lk
potenza
chiusura positiva
k>0
(o transitiva)
L∗ = L0 ∪ L+ = {} ∪ L+
chiusura di Kleene
(transitiva e riflessiva)
L∗ = {w1 . . . wn ∈ Σ∗ | n ∈ N ∀i ∈ {1, . . . , n} : wi ∈ L}
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
15 / 70
Linguaggi Formali [. . . cont.]
Altre operazioni
complemento L = {w ∈ Σ∗ | w 6∈ L}
intersezione L ∩ L0 = {w ∈ Σ∗ | w ∈ L ∧ w ∈ L0 }
riflessione LR = {wR | w ∈ L}
dove la stringa riflessa wR di una stringa w inverte
l’ordine dei simboli
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
16 / 70
Espressioni Regolari
Espressioni e linguaggi regolari:
1
è una ER
L() = {}
2
a è una ER per ogni a ∈ Σ
L(a) = {a}
3
(r) è una ER, per ogni ER r
L((r)) = L(r)
4
(r)|(s) è una ER, per ogni coppia di ER r, s
L((r)|(s)) = L(r) ∪ L(s)
5
(r) · (s) è una ER, per ogni coppia di ER r, s
L((r) · (s)) = L(r) · L(s)
6
7
(r)∗ è una ER, per ogni r
L((r)∗ ) = L(r)∗
nient’altro è una ER
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
17 / 70
Espressioni Regolari [. . . cont.]
Osservazioni
il simbolo di concatenazione “·” può essere omesso
le parentesi possono essere omesse essendo le op. associative
a sinistra e imponendo la precedenza: ∗ > · > |
Esempio
(((a)|(b))∗ ((a)|(b)))|(a)
si può scrivere in modo compatto come:
(a|b)∗ (a|b)|a
(((1)∗ )(0))|(2) si può scrivere 1∗ 0|2
Per ogni linguaggio possono esistere diverse ER che lo
denotano
Esempio L[(ab)∗ a] = L[a(ba)∗ ]
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
18 / 70
Espressioni Regolari [. . . cont.]
Esempi
i) ab|b definisce il linguaggio {ab, b}
ii) a(a|b)b definisce {aab, abb}
iii) a∗ sta per {an | n ≥ 0} = {, a, aa, aaa, aaaa, . . .}
iv) b∗ a|c denota per {bn a | n ≥ 0} ∪ {c}
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
19 / 70
Espressioni Regolari [. . . cont.]
Identità: si definisce una rel. d’equivalenza tra ER in base ai
linguaggi definiti:
r = s se e solo se L[r] = L[s]
Proprietà
r|r0 = r0 |r
commutatività di |
associatività di |
r|(r0 |r00 ) = (r|r0 )|r00
associatività di ·
r(r0 r00 ) = (rr0 )r00
elem. neutro per ·
idempotenza di
∗
r = r = r
r∗∗
= r∗
distributività a sinistra di · su |
r(r0 |r00 ) = rr0 |rr00
distributività a destra di · su |
(r|r0 )r00 = rr00 |r0 r00
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
20 / 70
Espressioni Regolari [. . . cont.]
Estensioni
rip. positiva r+ = rr∗ = r∗ r
possibilità r? = r|
elenco [a1 , . . . , an ] = a1 | · · · |an
dove ai ∈ Σ
se sussiste una rel. d’ordine tra i simboli:
[a1 -an ] = a1 | · · · |an
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
21 / 70
Linguaggi Regolari
Un linguaggio L è regolare se
L=∅
oppure
L = L(r)
per qualche espressione regolare r
Esempio Dato Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}
l’ER:
[0-9]+ (|.[0-9]+ )
denota il linguaggio dei numeri decimali (senza segno)
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
22 / 70
Linguaggi Regolari [. . . cont.]
Definizioni Regolari
dato Σ
d1
d2
..
.
:= r1
:= r2
.. ..
. .
dn := rn
dove di sono nuovi simboli e
ogni ri è una ER sull’alfabeto Σ ∪ {rj | 1 ≤ j ≤ i − 1}
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
23 / 70
Esercizi
1
ER per identificatori C
2
ER per numeri in notazione scientifica
es. 123.456E-7
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
24 / 70
Automi a Stati Finiti
Problema: riconoscere i lessemi ed associarli ai token
Automi Modelli astratti di macchine
in input su un nastro, fatto da celle contenenti un simbolo
ciascuna, stringhe su un dato alfabeto d’ingresso Σ
lettura L-to-R (con/senza terminatore)
un simbolo alla volta
una unità di controllo a stati finiti determina il
funzionamento della macchina
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
25 / 70
Automi a Stati Finiti [. . . cont.]
···
b
..
q3
q2
a
a
a
···
.
qn
δ
q1
N. Fanizzi ( LdP)
a
b
q0
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
26 / 70
Automi a Stati Finiti [. . . cont.]
Diagrammi di transizione per descrivere automi
Esempio
[0-9]
[0-9]
A
B
[0-9]
.
[0-9]
C
D
riconosce [0-9]+ (|.[0-9]+ )
accetta 23
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
27 / 70
Automi a Stati Finiti [. . . cont.]
Esempio
[0-9]
E
F
[0-9]
.
riconosce [0-9]+ (|.[0-9]+ ) ma anche altre stringhe
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
28 / 70
Automi a Stati Finiti [. . . cont.]
Esempio
riconoscere (a|b)∗ ba
a
0
b
1
a
2
b
non determinismo: nello stato 0 si legge b
per accettare deve esistere almeno un percorso che porti ad
uno stato finale
accetta bba e abba, rifiuta aabb
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
29 / 70
Automi Non-Deterministici
Un automa finito non deterministico (NFA) è una quintupla
hΣ, Q, δ, q0 , Fi dove
Σ è un alfabeto finito di simboli di input;
Q è un insieme finito di stati;
δ è la funzione di transizione
δ : Q × (Σ ∪ {}) → P(Q)
q0 ∈ Q stato iniziale;
F ⊆ Q stati finali
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
30 / 70
Automi Non-Deterministici [. . . cont.]
matrice di transizione:
δ
→ q0
∗q1
..
.
qm
Esempio
a1 a2 · · · an ···
···
..
.. . .
. .
. .. ..
.
.
···
automa precedente
δ
→0
1
∗2
N. Fanizzi ( LdP)
a
b
{0} {0, 1}
{2}
∅
∅
∅
∅
∅
∅
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
31 / 70
Automi Non-Deterministici [. . . cont.]
Un NFA N = hΣ, Q, δ, q0 , Fi accetta w = a1 · · · an sse
nel diagramma di transizione esiste un cammino da q0 a uno
stato di F nel quale w è esattamente la stringa che si ottiene
concatenando le etichette degli archi percorsi
Il linguaggio accettato da un NFA N è l’insieme
L[N] = {w ∈ Σ∗ | N accetta w}
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
32 / 70
Automi Non-Deterministici [. . . cont.]
formalmente:
δ ∗ : P(Q) × Σ∗ → P(Q)
δ ∗ (Qi , za) =
[
δ(q0 , a)
q0 ∈δ ∗ (Qi ,z)
δ ∗ (Qi , ) =
S
a∈Σ
w accettata sse:
δ(Qi , a)
∃q ∈ F : q ∈ δ ∗ ({q0 }, w)
L[N] = {w ∈ Σ∗ | δ ∗ ({q0 }, w) ∩ F 6= ∅}
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
33 / 70
Automi Non-Deterministici [. . . cont.]
2
a
4
0
6
1
7
b
8
a
9
3
b
5
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
34 / 70
Automi Deterministici
Un automa finito deterministico (DFA) è una quintupla
hΣ, Q, δ, q0 , Fi dove
Σ è un alfabeto finito di simboli di input;
Q è un insieme finito di stati;
δ è la funzione di transizione
δ :Q×Σ→Q
q0 ∈ Q (lo stato iniziale);
F ⊆ Q (gli stati finali).
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
35 / 70
Automi Deterministici [. . . cont.]
a
B
a
a
A
D
b
b
b
a
b
N. Fanizzi ( LdP)
C
DFA per (a|b)∗ ba
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
36 / 70
Equivalenza
Dato un linguaggio accettato da un NFA è sempre possibile
costruire un DFA per lo stesso linguaggio?
Dato un NFA, sia q ∈ Q: la -chiusura di q (-clos(q)) è il più
piccolo insieme di stati raggiungibili via -transizioni:
q ∈ -clos(q) e se p ∈ -clos(q) allora δ(p, ) ⊆ -clos(q)
Per estensione, sia P ⊆ Q
-clos(P) =
[
-clos(p)
p∈P
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
37 / 70
Equivalenza [. . . cont.]
Calcolo -clos(P)
1
2
T ← P; // iniz.
-clos(P) ← P; // iniz.
3
4
5
6
7
8
9
10
11
12
while T 6= ∅ {
scegli r ∈ T;
T ← T \ {r};
foreach s ∈ δ(r, )
if (s ∈
/ -clos(P)) {
-clos(P) ← -clos(P) ∪ {s};
T ← T ∪ {s};
}
}
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
38 / 70
Equivalenza [. . . cont.]
Mossa (non deterministica)
mossa : P(Q) × Σ → P(Q)
mossa(P, a) =
[
δ(p, a)
p∈P
Dallo stato q, consumando a,
un NFA potrà transitare in uno degli stati in
-clos(mossa(-clos({q}), a))
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
39 / 70
Equivalenza [. . . cont.]
Costruzione Sottinsiemi
sia N = hΣ, Q, δ, q0 , Fi
1
2
S ← -clos(q0 ); // insieme di stati
T ← {S}; // insieme di insiemi non ancora marcati
3
4
5
6
7
8
9
10
11
while ∃P ∈ T non marcato {
marca P;
for each a ∈ Σ {
R ← -clos(mossa(P, a));
if R ∈
/ T { T ← T ∪ {R}; } // aggiunto non marcato
definisci ∆(P, a) = R;
}
}
Si definisce il DFA MN = hΣ, T , ∆, -clos(q0 ), F i
dove F = {R ∈ T | R ∩ F 6= ∅}
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
40 / 70
Equivalenza [. . . cont.]
Esempio
2
0
4
6
1
3
N. Fanizzi ( LdP)
a
b
7
b
8
a
9
5
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
41 / 70
Equivalenza [. . . cont.]
a
B
stati NFA
{0, 1, 2, 3, 7}
{1, 2, 3, 4, 6, 7}
{1, 2, 3, 5, 6, 7, 8}
{1, 2, 3, 4, 6, 7, 9}
stato DFA
A
B
C
D
a
a
A
D
b
b
b
a
b
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
C
18 marzo 2015
42 / 70
Equivalenza [. . . cont.]
Teorema
Sia N = hΣ, Q, δ, q0 , Fi un NFA e sia MN il DFA ottenuto con la
costruzione per sottinsiemi. Risulta che
L[N] = L[MN ]
Teorema
La classe dei linguaggi riconosciuti dagli NFA coincide con la classe
dei linguaggi riconosciuti dai DFA.
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
43 / 70
Corrispondenza Automi-ER
Teorema
Data un’espressione regolare r, si può costruire un NFA Nr tale che
L[r] = L[Nr ]
Dim. per induzione
r≡
r≡a
N. Fanizzi ( LdP)
a
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
44 / 70
Corrispondenza Automi-ER [. . . cont.]
is
r ≡ s|t
fs
f
i
it
r ≡ st
N[s]
is
N. Fanizzi ( LdP)
N[s]
N[t]
fs /it
ft
N[t]
Analisi Lessicale: Linguaggi Regolari
ft
18 marzo 2015
45 / 70
Corrispondenza Automi-ER [. . . cont.]
r ≡ s∗
i
N. Fanizzi ( LdP)
is
N[s]
fs
Analisi Lessicale: Linguaggi Regolari
f
18 marzo 2015
46 / 70
Grammatiche Regolari
Una grammatica libera è regolare sse ogni produzione ha la
forma
V −→ aW
oppure
V −→ a
con V, W ∈ NT e A ∈ T.
Per S è ammessa anche S −→ N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
47 / 70
Grammatiche Regolari [. . . cont.]
Esempio Sia G = h{A, B, C}, {a, b}, A, Ri
con R dato da
A −→ aA|bB,
B −→ bB|aC|a,
C −→ aA|bB
Grammatica regolare tale che L[G] = (a|b)∗ ba
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
48 / 70
Grammatiche Regolari [. . . cont.]
Teorema
Da un DFA M si può definire una grammatica regolare GM tale che
L[M] = L[GM ]
Dim. Sia M = hΣ, Q, δ, q0 , Fi il DFA.
La grammatica GM = hQ, Σ, R, q0 i ha:
non terminali, gli stati di M;
terminali: l’alfabeto di M;
simbolo iniziale: lo stato iniziale q0 ;
produzioni R:
per ogni δ(qi , a) = qj :
qi −→ aqj ∈ R e
qi −→ a ∈ R se qj ∈ F
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
49 / 70
Grammatiche Regolari [. . . cont.]
Esempio
dato
a
B
a
a
A
D
b
b
b
a
b
C
la grammatica corrispondente G = h{A, B, C, D}, {a, b}, A, Ri
con R dato da
A −→ aB | bC,
B −→ aB | bC,
C −→ aD | a | bC,
D −→ aB | bC
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
50 / 70
Grammatiche Regolari [. . . cont.]
Teorema
Il linguaggio definito da una grammatica regolare G è un
linguaggio regolare: è vuoto, oppure è possibile costruire
un’espressione regolare rG tale che
L[G] = L[rG ]
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
51 / 70
Grammatiche Regolari [. . . cont.]
N. Fanizzi ( LdP)
ESPRESSIONI
REGOLARI
NFA
GRAMMATICHE
REGOLARI
DFA
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
52 / 70
Indistinguibilità
Siano q1 e q2 due stati di un DFA e x ∈ Σ∗ .
La stringa x distingue q1 e q2 sse
i) il cammino che parte in q1 e consuma x arriva in uno stato
finale, mentre il cammino che parte in q2 e consuma x arriva
in uno stato non finale;
ii) oppure, viceversa, il cammino che parte in q1 e consuma x
arriva in uno stato non finale, mentre il cammino che parte
in q2 e consuma x arriva in uno stato finale.
Due stati sono indistinguibili se nessuna x ∈ Σ∗ li distingue
La rel. di indistinguibilità è una relazione d’equivalenza
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
53 / 70
Indistinguibilità [. . . cont.]
distingue ogni stato in F da
ogni stato in Q \ F,
quindi sono distinguibili:
{A, D}, {B, D} e {C, D}
Esempio
a
B
a
a
A
a distingue B da C
D
b
b
b
a
b
C
essendo δ(B, a) = B
mentre δ(C, a) = D,
e {B, D} già distinguibili
e anche {A, C} e {C, D}
b non distingue alcuna coppia
Osservazione
A e B indistinguibili: da entrambi gli stati
le stringhe che iniziano con a portano a B
le stringhe che iniziano con b portano a C
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
54 / 70
Tabella a Scala
Sia M = hΣ, Q, δ, q0 , Fi un DFA.
Un elemento (p, q) della tabella può contenere:
nulla: p e q non sono ancora distinti;
X : p e q sono distinguibili;
alcune coppie (p0 , q0 ):
se p e q sono distinguibili, allora tutte le (p0 , q0 ) saranno
distinguibili
Esempio
q1
q2
q3
q0 q1 q2
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
55 / 70
Tabella a Scala [. . . cont.]
Algoritmo di riempimento
1
marca X ogni (p, q) tale che p ∈ F e q ∈ Q \ F o viceversa;
2
per ogni altra (p, q):
se esiste un a ∈ Σ con (δ(p, a), δ(q, a)) già marcata X:
i. marca (p, q) con X;
ii. marca con X tutte le coppie elencate in (p, q),
e procedi ricorsivamente la marcatura su tutte le coppie
marcate in questo modo;
altrimenti, per ogni a ∈ Σ tale che δ(p, a) 6= δ(q, a),
metti (p, q) nella lista di (δ(p, a), δ(q, a)).
3
sia J l’insieme delle coppie che non contengono X
4
la relazione di indistinguibilità è
I = J ∪ {(q, q) | q ∈ Q} ∪ {(q, p) | (p, q) ∈ J}
chiusura riflessiva e simmetrica di J
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
56 / 70
Tabella a Scala [. . . cont.]
B
C
D
A B C
(a)
B
C
D X X X
A B C
(b)
B
C X X
D X X X
A B C
(c)
(a) inizio
(b) marca (D, A), (D, B), (D, C) distinti da (c) marca (C, A) e (C, B) distinti da a
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
57 / 70
Tabella a Scala [. . . cont.]
Teorema
Dato un DFA M = hΣ, Q, δ, q0 , Fi, l’algoritmo di riempimento della
tabella a scala termina. Due stati p e q sono distinguibili se e solo
se la casella (p, q) (o (q, p)) è marcata con X.
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
58 / 70
Automa Minimo
Dato il DFA M = hΣ, Q, δ, q0 , Fi,
l’automa minimo equivalente Mmin = hΣ, Qmin , δmin , [q0 ], Fmin i
è dato da:
Qmin = Q/I insieme delle classi di equivalenza [q] della
relazione di indistinguibilità I
δmin ([q], a) = [δ(q, a)]
Fmin = {[q] | q ∈ F}
Teorema
Dato un DFA M = hΣ, Q, δ, q0 , Fi, l’automa Mmin riconosce lo
stesso linguaggio di M, ed ha il minimo numero di stati tra tutti gli
automi per questo linguaggio
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
59 / 70
Automa Minimo [. . . cont.]
Esempio
dato il DFA
→A
B
C
∗D
E
F
G
H
0
B
A
D
D
D
G
F
G
da cui si ricava:
N. Fanizzi ( LdP)
la tabella a scala risultante è:
B X
C X X
D X X X
E X X
X
F X
X X X
G
X X X X X
H X X X X X X X
A B C D E F G
1
A
C
B
A
F
E
G
D
→ A, G
B, F
C, E
∗D
0
1
B, F A, G
A, G C, E
D
B, F
D
A, G
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
60 / 70
Automa Minimo [. . . cont.]
Esempio
DFA:
[Ausiello et al.]
→∗0
∗1
2
3
4
5
6
a
1
0
4
0
2
2
1
b
2
5
3
5
6
6
5
tabelle a scala risultanti
(iniziale/finale)
N. Fanizzi ( LdP)
1
2
3
4
5
6
1
2
3
4
5
6
X
X
X
X
X
0
X
X
X
X
X
1
2
3
4
5
X
4
X
5
(3,6)
X
X
X
X
X
0
X
X
X
X
X
1
Analisi Lessicale: Linguaggi Regolari
X
(2,5)
(0,1)
X
2
X
X
(2,4)
(2,5)
3
18 marzo 2015
61 / 70
Automa Minimo [. . . cont.]
Indistinguibili
I = {(0, 1), (2, 4), (2, 5), (4, 5), (3, 6)}
quindi
Q/I = {{0, 1}, {2, 4, 5}, {3, 6}}
da cui si ricava:
N. Fanizzi ( LdP)
→ ∗[0]
[2]
[3]
a
b
[0] [2]
[2] [3]
[0] [2]
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
62 / 70
Pumping Lemma per Linguaggi Regolari
Teorema (Pumping Lemma – linguaggi regolari)
Sia L un linguaggio regolare. Esiste una costante N > 0 tale che,
ogni z ∈ L con |z| ≥ N può essere suddivisa in tre sottostringhe
z = uvw tali che
(i) |uv| ≤ N;
(ii) v 6= ;
(iii) per ogni k ≥ 0, uvk w ∈ L
Inoltre N è minore o uguale del numero di stati del DFA minimo che
accetta L
Osservazioni
condizione necessaria ma non sufficiente
può essere usata per dimostrare che un linguaggio non è
regolare
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
63 / 70
Pumping Lemma per Linguaggi Regolari [. . . cont.]
Dim. (cenni) Si considera un DFA tale che L(M) = L con
N = |Q| e z ∈ L, z = a1 a2 · · · al con l ≥ N
Percorso d’accettazione di z (sequenza di stati q(0) , q(1) , . . . , q(l) ):
q(0)
a1
q(1)
a2
···
ai
q(i)
ai+1
···
al
q(l)
con q0 = q(0) e q(l) ∈ F
Sono l + 1 stati ma |z| = l ≥ N = |Q|
quindi c’è (almeno) uno stato ripetuto nella sequenza:
∃i, j ∈ {0, . . . , l} : q(i) = q(j) con i < j e (i + j) ≤ N
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
64 / 70
Pumping Lemma per Linguaggi Regolari [. . . cont.]
q(0)
u
a1 · · · ai
q(i)
q(j)
w
aj+1 · · · al
q(l)
v
ai+1 · · · aj
z = uvw e q(l) ∈ F costituisce uno stato di accettazione per uvvw,
uvvvw, ecc., . . . dunque ∀k ≥ 0 uvk w ∈ L(M)
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
65 / 70
Pumping Lemma per Linguaggi Regolari [. . . cont.]
Esempio L = {an bn | n ≥ 0}
Supponiamo che sia regolare
Deve valere il P.L. quindi si considera N ≥ 0 non noto, ma fissato
Scegliamo uno specifico z tale che
|z| ≥ N :
z = aN bN
Per ogni scomposizione u, v, w si ha che
(i) |uv| ≤ N
(ii) |v| ≥ 1
Quindi v = ah con 1 ≤ h ≤ N
Scegliendo uno specifico numero di ripetizioni di v,
k = 2, risulta:
uvvw = aN+h bN ∈
/L
che contraddice la tesi (iii) del P.L.
Quindi L non può essere regolare
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
66 / 70
Pumping Lemma per Linguaggi Regolari [. . . cont.]
Esempio [Linz] Dimostrare che
L = {w ∈ {a, b}∗ | na (w) 6= nb (w)} non è regolare.
Si assuma, per assurdo, che L sia regolare.
Allora, per un certo n, si consideri
z = an! b(n+1)! ∈ L
in modo che |z| > n.
In base al P.Lemma, ∃u, v, w tali che z = uvw e
|uv| ≤ n,
|v| ≥ 1
∀i ≥ 0 : uvi w ∈ L
Poiché dev’essere k = |v| ≤ |uv| ≤ n, sarà v = ak .
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
67 / 70
Pumping Lemma per Linguaggi Regolari [. . . cont.]
Quindi le stringhe gonfiate avranno la forma:
an!−k (ak )i b(n+1)!
i = 0, 1, . . .
Esse rientrano nel tipo am bm 6∈ L (con m = (n + 1)!)
se n! − k + ki = (n + 1)!, ossia se
i=
(n + 1)! − n! + k
k
=
((n + 1) − 1)n!
k
+
k
k
=
n · n!
k
+1∈Z
ma ciò è sempre valido, essendo k ≤ n.
Quindi L non può essere regolare.
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
68 / 70
Esercizi
1
es.3 cap.3
2
es.2 cap.3
3
es.1 cap.3
4
5
Dato L = {aaa} ∪ {a2k | k ≥ 0}, scrivere un NFA N tale che
L(N) = L, ricavare un DFA M equivalente minimale e fornire
la grammatica G tale che L[M] = L[G] = L
Dimostrare che non sono regolari i segg. linguaggi:
a.
b.
c.
d.
{w ∈ {a, b}∗ | na (w) = nb (w)}
k
{an b | n > k}
m
{an b ck | n > k, n, m, k > 0}
m
{an b ck | m > k, n, m, k > 0}
Si vedano anche i testi consigliati sui ling. formali
N. Fanizzi ( LdP)
Analisi Lessicale: Linguaggi Regolari
18 marzo 2015
69 / 70
Riferimenti
M. Gabbrielli, S. Martini: Linguaggi di programmazione.
Principi e paradigmi, 2/e. McGraw-Hill. 2011
Hopcroft, Motwani, Ullman: Automi, Linguaggi e
Calcolabilità, Pearson Italia, 3/a Ed. (sito) [capp. 1-7]
Ausiello, d’Amore, Gambosi: Linguaggi, Modelli, Complessità,
FrancoAngeli
Linz: An Introduction to Formal Languages and Automata, 5th
Ed. Jones & Bartlett