Automi finiti deterministici (DFA) (1)
Un DFA è una quintupla (Q, S, d, q0 , F) dove:
Q è un insieme finito di stati
S è un alfabeto finito di input
q0  Q è lo stato iniziale
F  Q è l’insieme degli stati finali
d è la funzione di transizione Q  S  Q.
d^ è l’estensione di d a stringhe, tale che
d^ (q, e) = q
d^ (q, wa) = d (d^ (q, w), a)
Poiché d^ (q, a) = d (d^ (q, e), a) = d (q, a) non c’è disaccordo
tra d e d^ dove sono entrambe definite e scriveremo d per d^.
Automi finiti deterministici (DFA) (2)
Una stringa x è accettata da un DFA M = (Q, S, d, q0 , F) se
d(q0 , x) = p per un p  F.
Definiamo linguaggio accettato da M l’insieme di stringhe
L(M) = {x | d(q0 , x)  F}.
Il linguaggio accettato da un DFA è detto linguaggio regolare.
Diagrammi di transizione
A un DFA è associato un grafo (chiamato diagramma di
transizione) tale che i nodi corrispondono agli stati del DFA
e se c’è una transizione dallo stato p allo stato q sull’input
a allora nel grafo c’è un arco dal vertice corrispondente a
p al
vertice corrispondente a q.
1
Esempio
.
0
1
0
0
0
1
1
Lo stato iniziale è anche finale. Se il controllo è in uno degli
stati superiori si è letto un numero pari di 0, se è in uno degli stati
a sinistra si è letto un numero pari di 1.
Automi finiti non deterministici (NFA) (1)
Un NFA è una quintupla M = (Q, S, d, q0 , F) dove:
Q, S, q0 , F sono come nel DFA e d : Q  S  2Q.
d^ è l’estensione di d a stringhe, tale che
d^(q, e) = {q}
d^(q, wa) = {p | per qualche r  d^(q, w) p  d (r, a)}.
Poiché d^(q, a) = d(q, a) scriveremo d per d^.
Si può estendere d ad argomenti in 2Q  S*
d (P, w) =  q  P d(q, w) per P  Q.
Una sequenza di input a1 a2 … an è accettata da un NFA se esiste
una sequenza di transizioni corrispondente alle sequenza di input
che porta dallo stato iniziale a uno stato finale.
Per M = (Q, S, d, q0 , F), L(M) = {w | d^(q0, w) contiene uno stato
in F}.
Automi finiti non deterministici (NFA) (2)
1
0
0
0
.
1
0
Esempio.
1
.
1
0
1
L’automa accetta tutte le stringhe di 0 e 1 con due 0 oppure due 1
consecutivi.
Equivalenza di NFA e DFA (1)
Teorema. Sia L l’insieme accettato da un NFA. Esiste un DFA che
accetta L.
Prova. Sia M = (Q, S, d, q0 , F) un NFA che accetta L. Sia Sia
M’ = (Q’, S, d’, q0’, F’) un DFA tale che:
Q’= 2Q un elemento di Q’ è denotato [q1 , q2 , …, qi ]
F’ è l’insieme di tutti gli stati in Q’ contenenti uno stato finale di M
q0’= [q0 ]
d’([q1 , q2 , …, qi ], a) = [p1 , p2 , …, pj ] se e solo se
d({q1 , q2 , …, qi}, a) = {p1 , p2 , …, pj }.
Mostriamo per induzione sulla lunghezza della stringa di input x
che d’(q0’, x) = [q1 , q2 , …, qj ] se e solo se d(q0, x) = {q1 , q2 , …, qj }.
Equivalenza di NFA e DFA (2)
Base. Immediato per |x| = 0 perché q0’= [q0 ] e x deve essere e.
Passo. Assumiamo la tesi vera per |x|<= m e consideriamo la
stringa xa con a  S. Per ipotesi di induzione
d’(q0’, x) = [p1 , p2 , …, pj ] se e solo se d(q0, x) = {p1 , p2 , …, pj }.
Per definizione di d’ si ha d’([p1 , p2 , …, pj ], a) = [r1 , r2 , …, rk ]
se e solo se d({p1 , p2 , …, pj}, a) = {r1 , r2 , …, rk}. Quindi infine
d’(q0’, xa) = [r1 , r2 , …, rk ] se e solo se d(q0, xa) = {r1 , r2 , …, rk }.
Inoltre d’(q0’, x)  F’ esattamente quando d (q0, x) contiene uno
stato in F. Perciò L(M) = L(M’).
Equivalenza di NFA e DFA (3)
Esempio. M = ({q0 , q1}, {0 , 1}, d, { q1})
con d(q0, 0) = {q0 , q1}, d(q0, 1) = {q1}, d(q1, 0) =  , d(q1,1) = {q0, q1}
.
1
0
0
q0
1
1
M’ = (Q, {0 , 1}, d’, [q0 ], F) con Q = {[q0 ], [q1 ], [q0, q1 ], }
d’([q0], 0) = [q0, q1], d’(q0,1) = [q1], d’(q1,0) =  , d’(q1,1) = [q0, q1]
d’([q0, q1], 0) = [q0, q1], d’([q0, q1],1) = [q0, q1], d’(, 0) = d’(, 1) = 
F = {[q1], [q0, q1]}
1
[q0]
0
.
0
[q1]
0
[q0, q1]
1
NFA con e transizioni (1)
Si considera una funzione di transizione d : Q  (S  {e}) 2Q.
Esempio. L’automa accetta le stringhe di un numero finito di 0
seguito da un numero finito di 1 seguito da un numero finito di 2.
e
0
e
1
.
2
e-closure(p)è l’insieme di tutti i vertici q tali che c’è un cammino da
p a q etichettato e
e-closure(P) =  p  P e-closure(p)
d^(q, e) = e-closure(q)
d^(q, wa) = e-closure({p | $r  d^(q, w) p  d (r, a)}.
Osservazione. d^(q, a) non è necessariamente uguale a d(q,a).
NFA con e transizioni (2)
Teorema. Se L è accettato da un NFA con e-transizioni allora L è
accettato da un NFA senza e-transizioni.
Prova. Dato M = (Q, S, d, q0 , F) NFA con e-transizioni costruiamo
M’ = (Q, S, d’, q0 , F’) senza e-transizioni d’(q,a) = d^(q,a) e
F’ = F{q0} se e-closure(q0 ) contiene uno stato in F e F’= F
altrimenti.
Proviamo d’(q0,x) = d^(q0,x) per induzione su |x|. Poiché d’(q0,e)=
{q0} mentre d^(q0, e) = e-closure(q0 ) può non essere vero per x = e.
Base: |x|=1 d’(q0,a) = d^(q0,a) per definizione
Passo: |x|>1 d’(q0,wa) = d’(d’(q0,w),a) . Per ipotesi di induzione
d’(q0,w) = d^(q0,w) = P. Dobbiamo mostrare d’(P,a) = d^(q0,wa).
Si ha d’(P,a) =  q  P d^(q,a) per la base dell’induzione
= d^(q0,wa) per definizione di d^.
NFA con e transizioni (3)
Dobbiamo ora mostrare che d’(q0,x) contiene uno stato di F’ se e solo
se d^(q0,x) contiene uno stato di F.
Se x = e d’(q0,e) = {q0 } e è posto in F’ ogni volta che d^(q,e) =
e-closure(q0 ) contiene uno stato in F. Se non x = e se d^(q0,x)
contiene uno stato in F allora d’(q0,x) contiene lo stesso stato in F’.
Viceversa, se d’(q0,x) contiene uno stato in F’ diverso da q0 , allora
d^(q0,x) contiene uno stato in F. Infatti se d’(q0,x) contiene q0 e q0 non
è in F, allora per definizione di d^ lo stato in e-closure(q0 ) e in F
deve essere in d^(q0,x).
NFA con e transizioni (4)
Esempio. Dato l’automa
e
.
e
0
1
2
La funzione è la seguente:
d^(q0,0)={q0,q1,q2}, d^(q0,1)={q1, q2}, d^(q0,2)={q2}
d^(q1,0)= , d^(q1,1)={q1, q2}, d^(q1,2)={q2}
d^(q2,0)= , d^(q2,1)= , d^(q2,2)={q2}
L’automa senza e transizioni è il seguente:
0
.
1
0,1
0,1,2
1,2
.
2
Proprietà di chiusura degli insiemi regolari (1)
Teorema. Gli insiemi regolari sono chiusi per unione,
concatenazione, chiusura di Kleene.
Proprietà di chiusura degli insiemi regolari (2)
Teorema. Gli insiemi regolari sono chiusi per complementazione,
ossia se L è regolare anche S*-L è regolare.
Prova. Sia L accettato dall’automa M = (Q, S, d, q0, F). Prendiamo
M’ = (Q, S, d, q0, Q-F). Allora M’ accetta una parola w se e solo se
d(q0,w) è in Q-F, cioè se w  S*-L.
Teorema. Gli insiemi regolari sono chiusi per intersezione.
Prova. Siano M1 = (Q1, S, d1, q1, F1) e M2 = (Q2, S, d2, q2, F2).
L’automa M = (Q1  Q2, S, d, [q1, q2], F1  F2)
con d([p1,p2],a) = [d1(p1, a),d2(p2, a)] accetta L(M) = L(M1)  L(M2).
La tesi segue anche dalla chiusura per unione e per
complementazione. Infatti L1 L2 = (L1C  L2C )C .
Proprietà di chiusura degli insiemi regolari (3)
Una sostituzione f : S  2D* è un’applicazione di un alfabeto S su
un sottoinsieme di D* per un alfabeto D. L’applicazione è estesa a
stringhe
f(e) = e
f(xa) = f(x) f(a)
e a linguaggi
f(L)= xL f(x)
Esempio. Sia f(0) = a, f(1) = b*. Allora f(01) = ab*.
Se L = 0*(0+1)1* allora f(L) = a*(a+b*)(b*)* = a*b*.
Proprietà di chiusura degli insiemi regolari (4)
Teorema. La classe degli insiemi regolari è chiusa per sostituzione.
Prova . Sia R  S* un insieme regolare e per ogni a  S sia f : S 
2D* la sostituzione tale che f(a) = Ra. Osserviamo che la sostituzione
di unione, prodotto, chiusura è unione, prodotto, chiusura della
sostituzione. La prova si fa per induzione sul numero di operatori
nell’espressione regolare.
Un omomorfismo h è una sostituzione tale che h(a) contiene una
sola stringa per ciascun a. L’immagine omomorfica di un linguaggio
L è h-1(L)= {x | h(x)  L}. Per una stringa w h-1(w)= {x | h(x) = w}.
Proprietà di chiusura degli insiemi regolari (5)
Esempio. Prendiamo h tale che h(0) = aa, h(1)= aba.
Allora h(0101) = aaabaaaaba.
Se L1 = (01)* allora h(L1) = (aaaba)*.
Se L2 = (ab+ba)*a allora h-1(L2) = {1} (è la sola stringa tale che
h(x) = y con y  L2).
Osservazione. h(h-1(L2)) = {aba}  L2
Con l’omomorfismo h(0) = a, h(1) = aa h -1(h (L1)) = (01+10)*  L1.
In generale
h(h-1(L))  L
h -1(h (L))  L1
Proprietà di chiusura degli insiemi regolari (6)
Teorema. La classe degli insiemi regolari è chiusa per omomorfismo
e omomorfismo inverso.
Prova. La chiusura per omomorfismo segue dalla chiusura per
sostituzione di cui è un caso particolare.
Per la chiusura inversa prendiamo M = (Q, S, d, q0, F) che accetta L.
Sia h un omomorfismo da D in S*. Prendiamo M = (Q’, S, d’, q0, F)
con d’(q,a) = d(q, h(a)) per q  Q, a  D.
Per induzione su |x| si ha d’(q0,x) = d(q0,h(x)). Quindi M’ accetta x se
e solo se M accetta h(x), cioè L(M’) = h-1(L (M)).
Applicazione della chiusura per omomorfismo e per
omomorfismo inverso
Sappiamo che {0n1n | n ≥ 1} non è regolare. Mostriamo che anche
{anban | n ≥ 1} non è regolare facendo vedere che si può trasformare in
{0n1n | n ≥ 1} con operazioni che preservano la regolarità.
Prendiamo due omomorfismi h1, h2 tali che
h1(a) = a h1(b) = ba h1(c) = a
h2 (a) = 0 h2 (b) =1
h2 (c) =1
Si ha
h1-1({anban | n ≥ 1})  a*b*c*= {anbcn-1 | n ≥ 1}
h2 (h1-1({anban | n ≥ 1})  a*b*c*) = {0n1n | n ≥ 1}
Se {anban | n ≥ 1} fosse regolare, poiché omomorfismi, omomorfismi
inversi e intersezione preservano la regolarità ne seguirebbe che
{0n1n | n ≥ 1} è regolare, che è una contraddizione.
Proprietà di chiusura degli insiemi regolari (7)
Il quoziente di due linguaggi L1 e L2, denotato L1/L2, è
{x | $ y  L2 tale che xy  L1 }.
Esempi.
Prendiamo L1 = 0*10*, L2 = 10*1. Poiché ogni y in L2 ha due 1 e
ogni stringa in L1 ha un solo 1, non c’è x tale che xy  L1, y  L2.
Prendiamo L1 = 0*10*, L2 = 0*1. Allora L1/L2 = 0* poiché per oni
x in 0* possiamo prendere y uguale a 1.
Proprietà di chiusura degli insiemi regolari (8)
Teorema. La classe degli insiemi regolari è chiusa per quoziente
con insiemi arbitrari.
Prova. Sia M = (Q, S, d, q0, F) un automa che accetta un insieme
regolare R. Sia L un linguaggio arbitrario. Il quoziente R/L è
accettato da un automa M’ = (Q, S, d, q0, F’) che si comporta come
M tranne che gli stati finali di M’ sono tutti gli stati di M tali che
esiste un y in L per cui d(q,y) è in F. La costruzione non è effettiva.
Proprietà decidibili degli insiemi regolari (1)
Teorema. L’insieme delle parole accettate da un automa finito M
con n stati è:
1. non vuoto se e solo se M accetta una stringa di lunghezza
minore di n
2. infinito se e solo se l’automa accetta qualche stringa di
lunghezza l con n  l < 2n.
Prova. 1.”se”: ovvio.
“solo se”: supponiamo che M accetti un insieme non
vuoto e che w sia una delle stringhe più corte accettate da M. Per il
pumping lemma deve essere |w| < n. Infatti se w fosse la parola
più corta con |w| ≥ n, allora sarebbe w = uxy e uy sarebbe la
stringa più corta accettata, contro l’ipotesi.
Proprietà decidibili degli insiemi regolari (2)
2. Se w  L(M) e n  |w| < 2n allora L(M) è infinito per il pumping
lemma. Infatti w = w1w2w3 e, per ogni i, anche w1w2iw3  L(M).
Viceversa, se L(M) è infinito esiste in L(M) w tale che |w| ≥ n.
Dobbiamo dimostrare che |w| < 2n. Se nessuna stringa è di
lunghezza compresa tra n e 2n-1, allora sia w di lunghezza almeno
2n ma di lunghezza uguale a quella delle parole più corte di
lunghezza almeno 2n. Allora per il pumping lemma possiamo
scrivere w = w1w2w3 con 1  |w2|  n e w1w3  L(M). Allora o w
non era una parola tra le più corte di quelle di lunghezza 2n o più
oppure |w1w3| è tra n e 2n-1. In ogni caso una contraddizione.
Per decidere se L(M) è vuoto basta controllare l’accettazione di
ogni stringa fino alla lunghezza n. Per decidere se il linguaggio è
infinito basta controllare l’appartenenza a L(M) di un parola di
lunghezza tra n e 2n-1. Basta anche controllare che il diagramma
abbia un ciclo.
Proprietà decidibili degli insiemi regolari (3)
Teorema. C’è un algoritmo per determinare se due automi finiti
sono equivalenti.
Prova. Siano M1, M2 due automi che accettano L1, L2
rispettivamente. Per le proprietà di chiusura per unione,
intersezione e complementazione (L1  L2C )  (L1C  L2 ) è
accettato da un automa finito M3 , ma M3 accetta una stringa se e
solo se L1 L2 .Quindi l’equivalenza è ridotta alla vuotezza, che è
decidibile.
Teorema di Myhill e Nerode (1)
Dato un linguaggio L definiamo una relazione RL tale che x RL y se
e solo se per ciascuno z o entrambi o nessuno di xz e yz è in L.
Osservazione. La relazione è sempre di indice finito, per il
pumping lemma, se il linguaggio è regolare.
La relazione può essere espressa in termini di automi. Dato un
DFA M = (Q, S, d, q0, F), per x, y  S* x RM y se e solo se d(q0,x)
= d(q0,y).
Proprietà. RM è una relazione di equivalenza. RM divide S* in
classi di equivalenza (una per ciascuno stato raggiungibile da q0).
RM è invariante destra rispetto alla concatenazione: se x RM y
allora per ogni z  S* xz RM yz, poiché d(q0, xz) = d(d(q0,x), z)
= d(d(q0,y), z) = d(q0, yz).
Teorema di Myhill e Nerode (2)
Teorema. Le asserzioni seguenti sono equivalenti:
1. L’insieme L è accettato da un automa finito.
2. L’insieme è l’unione di alcune classi di equivalenza di una
relazione di equivalenza invariante destra di indice finito.
3. La relazione di equivalenza RL sia definita da x RL y se e solo se
per ogni z  S* è xz  L esattamente quando yz  L. Allora RL è di
indice finito.
Prova. 1  2. Sia L accettato da un DFA M = (Q, S, d, q0, F).
Sia RM la relazione di equivalenza x RM y se e solo se d(q0,x) =
d(q0,y). RM è invariante destra perché per ogni z se d(q0,x) =
d(q0,y) allora se d(q0,xz) = d(q0,yz). L’indice è finito perché al più
uguale al numero degli stati in Q. L è l’unione di quelle classi di
equivalenza che includono stringhe x tali che d(q0,x) è in F.
Teorema di Myhill e Nerode (3)
2  3. Una relazione di equivalenza E che soddisfa (2) è un
raffinamento di RL, ossia ogni classe di E è contenuta in una classe di
RL. Quindi l’indice di RL non è più grande di quello di E e perciò è
finito. Assumiamo xEy. Poiché E è invariante destra, allora per ogni
z  S* xzEyz e quindi yz è in L se e solo se xz è in L. Quindi per
definizione di RL vale anche xRLy e quindi la classe di equivalenza di
x in E è contenuta nella classe di equivalenza di x in RL.
3  1. Mostriamo che RL è invariante destra. Supponiamo xRLy e
prendiamo w  S* . Allora dobbiamo provare xwRLyw. Poiché xRLy
allora per v qualsiasi xv  L se e solo se yv  L. Se prendiamo v = wz
è provato che è invariante destra. Sia Q’ l’insieme delle classi di
equivalenza di RL e [x] l’elemento di Q’ che contiene x. Definiamo
d’([x], a)=[xa]. Prendiamo q0’ = [e], F’={[x]| x in L}. L’automa M’ =
(Q’, S’, d’, q0’, F’) accetta L poiché d’(q0’,x)=[x] e cosí x  L(M’) se
e solo se x  F’.
Teorema di Myhill e Nerode (4)
Prendiamo l’automa
a
0
1
.
c
0
e
b
0
.
0
1
1
0
.
d
1
f
1
0,1
Assumiamo F = {c,d,e}. Tutti gli stati sono raggiungibili dallo stato
iniziale.
Le classi di equivalenza sono: ca = (00)*, cb = (00)*0, cc = (00)*1,
cd = (00)*01, ce = 0*100*, cf = 0*10*1(0+1)*.
L è l’unione delle classi cc, cd, ce.
Teorema di Myhill e Nerode (5)
La relazione RL per L ha x RLy se e solo se
x e y non hanno 1
x e y hanno ciascuno un 1
x e y hanno ciascuno più di un 1
(per esempio se x = 00 e y = 000 allora xz in L se e solo se z in
1+100*, ma questo vale anche per yz).
Denotiamo le tre classi c1 = 0*, c2 = 0*10*, c3 = 0*10*1(0+1)*.
Si ha c1 = ca  cb, c2 = cc  cd  ce , c3 = cf.
Da RL costruiamo un DFA. Prendiamo rappresentanti per c1, c2, c3,
ad esempio e, 1, 11. Prendiamo F ={[1]}. Per d’ abbiamo d’([1],0) =
[1] perché se w è in [1], ad esempio 0i10j, allora w0 è in 0i10j+1 che è
in c1.
[1]
[11]
[e]
1
0
.
0
1
0,1
Teorema di Myhill e Nerode (6)
Teorema. Il minimo automa che accetta L è unico a meno di
isomorfismo (ridenominazione degli stati) ed è dato da M’ come
costruito nella prova del teorema precedente.
Prova. Nella prova del teorema precedente si vede che un qualunque
DFA M = (Q, S, d, q0, F) che accetta L definisce una relazione di
equivalenza che è un raffinamento di RL. Così il numero di stati di M
è più grande o uguale al numero di stati dell’automa M’ che risulta
dalla costruzione. Se vale l’uguaglianza ciascuno stato di M può
essere identificato con uno degli stati di M’. Ossia, sia q uno stato di
M. Ci deve essere x in S* tale che d(q0,x) = q, altrimenti q potrebbe
essere rimosso e si potrebbe trovare un automa più piccolo.
Identifichiamo q con lo stato d(q0’,x) di M’. L’identificazione è
consistente. Infatti se d(q0,x) = d(q0,y) = q allora (per la prova del
teorema precedente) x e y sono nella stessa classe di equivalenza di
RL. Ne segue d’(q0’,x) = d’(q0’,y) = q e questo prova l’unicità.
Algoritmo per la costruzione dell’automa minimale (1)
Idea. Dato M = (Q, S, d, q0, F) sia  la relazione di equivalenza sugli
stati di M tale che p  q se e solo se, per ogni stringa di input x, d(p,x)
è uno stato accettore se e solo se d(q,x) è uno stato accettore.
Per il teorema c’è un isomorfismo tra le classi di equivalenza di 
che contengono gli stati raggiungibili da q0 per qualche stringa di
input e gli stati dell’automa minimale M’, cosí gli stati di M’ possono
essere identificati con queste classi.
Se p  q diciamo che p è equivalente a q. Diciamo che p è
distinguibile da q se esiste un x tale che d(p,x) è in F e d(q,x) no, e
viceversa. L’idea è di marcare inizialmente come distinti uno stato
finale e uno stato non finale e di procedere quindi marcando come
distinti due stati da cui per uno stesso simbolo di input si hanno
transizioni a due stati distinti.
Algoritmo per la costruzione dell’automa minimale (2)
Esempio. Consideriamo l’automa di esempio. Costruiamo una tabella
con un’entrata per ogni coppia di stati. Mettiamo una marca nella
tabella ogni volta che scopriamo che due stati non possono essere
equivalenti. Inizialmente marchiamo ogni entrata corrispondente a
uno stato finale e a uno non finale. Poi marchiamo coppie di stati da
uno dei quali andiamo a uno stato finale mentre dall’altro andiamo a
uno stato non finale.
b
c
d
e
f




a




b

c

d

e
Algoritmo per la costruzione dell’automa minimale (3)
Poiché d(f,1), d(a,2)) = (f,c) e (f,c) marcata, marchiamo (f,a) e
analogamente marchiamo (f,b). Così alla fine abbiamo
a  b, c  d  e.
Algoritmo
begin
1) for p in F and q in Q-F do mark (p,q);
2) for each pair of distinct states (p,q) in F  F or Q-F  Q-F do
3) if for some input symbol a, (d(p,a), d(q,a)) is marked then begin
4) mark (p,q);
5) recursively mark all unmarked pairs on the list for (p,q) and
on lists of other pairs that are marked at this step
end
else /* no pair (d(p,a), d(q,a)) is marked */
6) for all input symbols a do
7) put (p,q) on the list for (d(p,a), d(q,a)) unless d(p,a) = d(q,a)
end
Algoritmo per la costruzione dell’automa minimale (4)
Lemma (Complessità). Assumiamo che S abbia k simboli e Q abbia
n stati. La complessità dell’algoritmo è O(kn2).
Prova. La linea 1 richiede O(n2) passi. Il ciclo delle linee 2-7 è
eseguito O(n2) volte, al più una volta per ogni coppia di stati. Il
tempo totale speso nelle linee da 2 a 4, 6, 7 è O(kn2). Il tempo speso
in totale nella linea 5 è la somma delle lunghezze di tutte le liste, ma
ogni coppia è messa nella linea 7 in al più k liste, quindi il tempo
speso nella linea 5 è O(kn2), cosí il tempo totale è O(kn2).
Algoritmo per la costruzione dell’automa minimale (5)
Lemma (Correttezza della marcatura degli stati). Sia M = un DFA.
Allora p è distinguibile da q se e solo se l’entrata corrispondente alla
coppia (p,q) è marcata dall’algoritmo.
Prova. Assumiamo che p sia distinguibile da q e sia x la stringa più
breve che distingue p da q. Proviamo per induzione sulla lunghezza
di x che l’entrata (p,q) viene marcata. Se x è e allora esattamente uno
di p e q è finale e la coppia viene marcata nella linea 1. Assumiamo
l’ipotesi vera per |x| < i, 1  i, e |x| = i. Sia x=ay, t=d(p,a), u=d(q,a).
Ora, y distingue t da u e |y|=i-1, quindi la coppia (t,u) è marcata. Se
questo avviene dopo che (p,q) è già stata considerata o è marcata o è
nella lista associata a (t,u) e viene marcata (linea 5). Se (p,q) è
considerata dopo (t,u), allora (p,q) è marcata quando è considerata.
In tutti i casi viene marcata. Viceversa, assumiamo che (p,q) sia
marcata e facciamo vedere che p,q sono distinguibili. Perinduziojne
sul numero delle coppie.
Algoritmo per la costruzione dell’automa minimale (6)
Teorema. Il DFA costruito dall’algoritmo e rimuovendo stati
inaccessibili è il minimo DFA per il linguaggio che riconosce.
Prova. Sia M = (Q, S, d, q0, F) il DFA dato e M’ = (Q’, S, d’, [q0], F’)
il DFA costruito con Q’= {[q] | q accessibile da q0}, F’= {[q]| q  F},
d’([q],a) = d(q,a). La relazione d’ è definita consistentemente perché se
q  p allora d(p,a)  d(q,a), cioè se d(p,a) è distinto da d(p,a) da x,
allora ax distingue q da p. Per induzione su |w| si vede d’([q0],w) =
[d(q0,w)]. Ne segue L(M) = L(M’). Mostriamo che M’non ha più
statidi quante sono le classi di equivalenza di RL dove L = L(M). Se
non fosse cosí, ci sarebbero in q due stati accessibili q e p tali che non
q  p e tuttavia ci sono x e y tali che d(q0,x)=q e d(q0,y)=p e xRLy. Ma
allora q  p, perché se non fosse cosí qualche w in S* dovrebbe
distinguere p da q (per il lemma). Ma allora sarebbe falso xwRLyw
perché potremmo prendere z=e e osservare che esattamente uno di
xwz e ywz è in L. Ma poiché è invariante destra, si ha xwRLyw.
Quindi q e p non esistono, M’ non ha più stati dell’indice di RL.