CAPITOLUL II.
MAŞINI CU STĂRI FINITE
În acest capitol introducem conceptul de maşină cu stări finite,
numită şi automat finit. Aceste dispozitive matematice îşi au originea în
modelarea comportamentului circuitelor electronice secvenţiale;
utilizarea şi aplicarea lor este mult mai largă. Ele pot fi văzute ca cel mai
simplu model de „algoritm” sau a unui analizator de limbaj sau chiar a
unui calculator. Dispozitive mai sofisticate cum sunt automatele push-
down, sau maşinile Turing, pot fi văzute ca maşini cu stări finite cu
numeroase „clopoţei şi zurgălăi” ataşate lor. Teoria automatelor finite
este destul de simplă pentru a motiva o pătrunde mai adâncă în studiul
acestor modele avansate.
2.1. DEFINIŢII
Considerăm conceptul matematic de maşină cu stări finite (MSF),
sau automat finit (AF). Mai întâi acordăm atenţie maşinilor cu stări finite
deterministe (MSFD). Aceste maşini se compun dintr-un număr finit de
stări şi un dispozitiv de intrare, care citeşte simboluri, unul câte unul (de
la stânga la dreapta), dintr-un şir de caractere de intrare. Dacă maşina se
află într-o stare Q şi simbolul de intrare este x, ea îşi schimbă starea (sau
se mişcă) în starea ( , )Q xδ . Apoi citeşte următorul simbol de intrare din
dreapta iar procesul se repetă. Maşina se iniţializează într-o stare iniţială
0Q , iar primul simbol din şirul citit este cel mai din stânga simbol a
acestui şir. Regula ( , )Q xδ care descrie următoarea stare se numeşte
funcţie de tranziţie. Ea depinde doar de starea curentă Q şi de simbolul
curent x, deci este complet independentă de mişcările şi intrările
anterioare. Maşina se opreşte după ce a citit toate simbolurile şirului de
intrare. Unele variante ale conceptului de maşină admit ca funcţia ( , )Q xδ
să nu fie definită pentru unele stări Q sau simboluri x. În acest caz,
maşina se va opri şi când ajunge într-o configuraţie pentru care ( , )Q xδ nu
este definită. Înainte de a da definiţie formală vom parcurge câteva
exemple.
Exemplu 2.1. Se presupune că maşina M are patru stări: 0Q , 1Q , 2Q
şi 3Q . Şirurile de intrare admise sunt formate din simbolurile a, b şi c. Fie
0Q starea iniţială şi funcţia de tranziţie δ dată de tabela din figura 2.1.
Input curent
a B c
0Q 1Q 2Q 0Q
1Q 0Q 0Q 3Q
2Q 3Q 1Q 2Q
S
t
ă
r
i 3Q 3Q 1Q 0Q
Figura 2.1. Tabelul funcţiei de tranziţie.
Maşina poate fi reprezentată, în mod autoexplicativ, prin aşa
numita diagramă de stare sau diagramă de tranziţie corespunzătoare din
figura 2.2. Săgeata → indică că 0Q este starea iniţială. Observăm că în
unele cazuri maşina rămâne în aceeaşi stare, de exemplu 3 3( , )Q a Qδ = .
Aşadar, dacă maşina se află în starea 3Q şi simbolul de intrare este a,
maşina rămâne în starea 3Q şi următorul simbol va fi citit. Dacă input-ul
maşinii este aacbbca, maşina va trece prin următoarea secvenţă de
mişcări:
0 1 0 0 2 1 3 3
a a c b b c aQ Q Q Q Q Q Q Q→ → → → → → →
Aici x
i jQ Q→ înseamnă trecerea maşinii din starea iQ în jQ citind input-ul
x, ( , )i jQ x Qδ = . După ce a fost citit şirul de intrare maşina se află în starea
3Q .
Maşini cu stări finite sunt folosite pentru „recunoaşterea” sau
„acceptarea” diferitelor tipuri de şiruri şi respingerea altora, în funcţie de
starea maşinii după citirea şirului. Pentru o maşină cu stări finite M dată,
stabilim unele din stări drept „acceptate” sau „finale”. Când un şir
1 2... nx x xσ = este introdus în maşină, ea va executa secvenţa de mişcări
descrisă mai sus (începând cu starea iniţială 0Q şi simbolul 1x ). După
citirea simbolul nx , aflăm starea în care se opreşte maşina M.
Dacă starea curentă este o stare acceptată, vom spune că M acceptă σ , în
caz contrar M nu acceptă σ . În diagrama de tranziţie pentru M marcăm
stările acceptate cu un cerc dublu.
Starea iniţială poate fi o stare acceptată. O maşină în care aşa ceva are loc
va accepta şirul vid λ . (Poate accepta şi alte şiruri.)
Exemplu 2.2. Construim o maşină M care acceptă şiruri de
simboluri 0 şi 1 cu un număr par de 1-uri (şi nimic alt ceva). Diagrama de
tranziţie a maşinii este dată în figura 2.4. Aşadar, dacă avem ca input
1 01001011σ = secvenţa de mişcări este:
Figura 2.2. Diagramă de tranziţie.
Figura 2.3. Stare acceptată Q.
0 1 0 0 1 0 1 1
0 0 1 1 1 0 0 1 0Q Q Q Q Q Q Q Q Q→ → → → → → → →
Maşina se opreşte in starea acceptată 0Q , astfel 1σ este acceptat de M. Pe
de altă parte, dacă input-ul este 2 01101σ = secvenţa de mişcări va fi
0 1 1 0 1
0 0 1 0 0 1Q Q Q Q Q Q→ → → → → .
Starea 1Q în care se opreşte maşina, nu este o stare acceptată şi ca urmare
şirul 2σ nu este acceptat de M.
Figura 2.4. Diagrama de tranziţie a unui automat finit.
← Şir de intrare
Input curent – kxStare curentă – jQ
← Cap de citire
Figura 2.5. Reprezentare schematică a unei maşini cu stări finite.
Figura 2.5. arată o reprezentare schematică a maşinii cu stări finite.
Capul de citire se mişcă numai la dreapta; săgeata spre simbolul jQ indică
starea curentă. Definiţia formală a unei maşini cu stări finite este:
Definiţia 2.1. O maşină cu stări finite se compune din următoarele
obiecte:
1. O mulţime finită, nevidă 0 1Q { , , , }nQ Q Q= K . Elementele Q din Q
se numesc stări;
2. O mulţime finită, nevidă 1 2{ , , , }ka a aΣ = K de simboluri admise
în şirul de intrare. Mulţimea Σ se numeşte alfabetul de intrare
pentru M;
3. O stare desemnată 0 QQ ∈ , denumită stare iniţială;
4. O funcţie de tranziţie ( , )Q aδ definită pentru toţi QQ∈ şi a∈Σ .
Valoarea funcţiei ( , )Q aδ este o stare din Q, : Q Qδ ×Σ→ .
5. O mulţime nevidă F de stări din Q. Elementele din F se numesc
stări finale sau acceptate.
O maşină cu stări finite M va atunci un cvintet 0{Q, , , , F}M Q δ= Σ .
Pentru maşina din exemplul 2.2. avem 0 1Q { , }Q Q= , {0,1}Σ = ,
0 0Q Q= şi δ este dat prin 0 1 0( , 0) ( ,1)Q Q Qδ δ= = , 0 1 1( ,1) ( , 0)Q Q Qδ δ= = . În
literatura de specialitate există doar mici variaţii ale acestei definiţii.
Uneori nu este necesar ca funcţia de tranziţie ( , )Q xδ să fie definită pentru
toţi Q şi x; de asemenea mulţimea stărilor acceptate poate fi vidă.
Pentru a simplifica descrierea mişcărilor maşinii, introducem
conceptul de configuraţie. O configuraţie a unei maşini M este o pereche
,Q σ , unde Q este starea şi 1k k ma a aσ += K este partea şirului de intrare
care se află la dreapta şi sub capului de citire, vezi figura 2.6. Dacă
maşina M se află în configuraţia 1, k k mQ a a a+ K şi ˆ( , )kQ a Qδ = ,
următoarea configuraţia a maşinii M este 1 2ˆ , k k mQ a a a+ + K . Numim
aceasta mişcare şi o vom nota în felul următor:
1 1 2ˆ, ,k k m k k mQ a a a Q a a a+ + +→K K
Când şirul de intrare este vid, de exemplu după citirea întregului şir,
configuraţia maşinii M este ,Q λ , unde λ ia locul şirului vid. Ca urmare,
mişcarea maşinii din exemplul 2.2. cu input-ul 01101 este descrisă de
următoarea secvenţă de configuraţii:
Figura 2.6. Maşină cu stări finite în configuraţia 1, k k mQ a a a+ K .
←Şir de intrare
0 0 1 0 0 1, 01101 ,1101 ,101 , 01 ,1 ,Q Q Q Q Q Q λ→ → → → →
Dacă pentru o anumită secvenţă de configuraţii avem secvenţa de mişcări
1 1 2 2, , ,p pQ Q Qσ σ σ→ → →L
vom nota aceasta*
1 1, ,p pQ Qσ σ→
şi o numim tranziţie.
Exemplu 2.3. Maşina M are ca alfabet mulţimea {0,1, 2}Σ = . Fie
input-ul pentru M numerele întregii nenegativi exprimaţi în notaţie
ternară (în baza 3). Astfel, şirul 1 2 nε ε εK reprezintă numărul
2 11 2 13 3 3n
n n nx ε ε ε ε −− −= + ⋅ + ⋅ + ⋅L .
Maşina va accepta un şir 1 2 nε ε εK dacă şi numai dacă numărul
corespunzător lui x este par. Va accepta 121 ( 1 2*3 1*9 16= + + = , în baza
10) însă nu şi 210 ( 0 1*3 2*9 21= + + = , în baza 10). Comportamentul
maşinii corespunde următoarei reguli de paritate a numerelor exprimate
în notaţie ternară: dacă
2 11 2 13 3 3n
n n nx ε ε ε ε −− −= + ⋅ + ⋅ + ⋅L (2.1)
atunci x este par, dacă şi numai dacă 1 2 nε ε ε+ + +L este par. Pentru a
vedea aceasta, presupunem că x este dat de (2.1). Împărţirea cu 2 a
puterilor lui 3, dă restul 1. Astfel, când împărţim x cu 2, fiecare termen
3n kkε
−⋅ va contribui cu kε la rest. Demonstraţia formală se poate da cu
ajutorul congruenţelor. Maşina M corespunde atunci diagramei din figura
2.7.
Funcţia de tranziţie δ este dată astfel încât ( , )i jQ Qδ ε = , unde j este restul
obţinut în urma împărţirii lui i ε+ la 2 ( (mod 2)j i ε≡ + ). Cu input-ul de
forma 121σ = maşina trece prin secvenţa de configuraţii
0 1 1 0,121 , 21 ,1 ,Q Q Q Q λ→ → →
şi pentru 1122σ = mişcările sunt
0 1 0 0 0,1122 ,122 , 22 , 2 ,Q Q Q Q Q λ→ → → → .
Figura 2.7. Divizibilitatea cu 2.
2.2. DESCRIEREA UNUI LIMBAJ CU AJUTORUL MAŞINILOR
Conceptul de maşină cu stări finite permite o nouă metodă de
descriere a limbajelor. Fie M o maşină cu stări finite având alfabetul Σ .
Definim limbajul ( )L M generat de M ca mulţimea şirurilor de elemente
din Σ acceptate de M. Cu alte cuvinte, un şir 1 2 nx x xσ = K din *Σ va fi în
( )L M dacă şi numai dacă maşina M, pornită cu input-ul σ , se va opri
într-o stare acceptată. Formal avem:
Definiţia 2.2. Fie 0{Q, , , , F}M Q δ= Σ o maşină cu stări finite.
Limbajul ( )L M generat (recunoscut sau acceptat) de M este definit ca
{ }**
0( ) | , , unde FL M Q Q Qσ σ λ= ∈Σ → ∈ .
Descriere de mai sus a unui limbaj este foarte convenabilă. Maşini
cu stări finite por fi uşor simulate pe calculator, de fapt, ele pot fi uşor
implementate şi în componente hardware. Astfel, dat fiind un limbaj L
pentru care se poate construi o maşină cu stări finite, atunci, s-a obţinut,
de fapt, un analizator automat pentru L. În mod firesc apare următoarea
întrebare: Fiind dată o gramatică G, putem construi o maşină cu stări
finite M astfel încât ( ) ( )L G L M= ? Din nefericire (sau din fericire, în
funcţie de punctul de vedere), acest lucru este posibil doar pentru un tip
special de gramatici – gramaticile regulare. Reamintim că G este regulară
dacă este liniară la dreapta (producţiile sunt de forma A aB→ , A a→ sau
S λ→ ) sau liniară la stânga (producţiile sunt de forma A Ba→ , A a→ sau
S λ→ ). Avem următorul rezultat.
Teorema 2.1. Fie L un limbaj. Există o maşină cu stări finite M
astfel încât ( )L L M= dacă şi numai dacă există o gramatică regulară G
astfel ca ( )L L G= .
În cele ce urmează vom demonstra doar suficienţa. Fiind dată o
maşină cu stări finite M, construim o gramatică regulară G astfel încât
( ) ( )L M L G= . Pentru M avem: stările 0 1, , , nQ Q QK , alfabetul
1 2{ , , , }ka a aΣ = K , funcţia de tranziţie ( , )Q aδ , starea iniţială 0Q şi F
mulţimea stărilor finale. Gramatica G este construită astfel:
1. Alfabetul (mulţimea de terminale) este 1 2{ , , , }ka a aΣ = K .
2. Mulţimea neterminalelor este mulţimea simbolurilor din Q
( QN = ).
3. Simbolul de start în G este 0Q – starea iniţială a lui M.
4. Producţiile din G sunt formate după următoarele reguli:
I. Pentru fiecare tranziţie ( , )i jQ a Qδ = , unde jQ nu este o
stare finală, folosim producţia i jQ aQ→ .
II. Pentru fiecare tranziţie ( , )i jQ a Qδ = , unde jQ este o
stare finală, folosim producţiile i jQ aQ→ şi iQ a→ .
III. Dacă 0Q este a stare finală, folosim producţia 0Q λ→ .
Evident gramatică obţinută este regulară (liniară la stânga).
Exemplu 2.4. Fie M definită de diagrama din figura 2.8. Gramatica
corespunzătoare G este construită astfel:
0 0
0
1.2.
Q bQQ b
→ →
Regula II. 0 0
bQ Q→
0 03. Q aQ→ Regula I. 0 1
aQ Q→
04. Q λ→ Regula III. 0 FQ ∈
1 0
1
5.6.
Q aQQ a
→ →
Regula II. 1 0
q
Q Q→
1 2
1
7.8.
Q bQQ b
→ →
Regula II. 1 2
bQ Q→
2 19. Q aQ→ Regula I. 2 1
aQ Q→
2 0
2
10.11.
Q bQQ b
→ →
Regula II. 2 0
bQ Q→
Figura 2.8. Gramatică pentru o maşină cu stări finite.
Demonstraţia pentru ( ) ( )L M L G= este imediată. Presupunem că un
şir 1 2 px x xσ = K este acceptat de maşină. Secvenţa de configuraţii pentru
M va fi
Stare iniţială – 0QStări acceptate – 0Q şi 1Q
0 1 2 1 2 3 2 3 4
*
1 2 1 2
*
1
ˆ ˆ, , ,
ˆ ˆ, ,
ˆ ˆ, ,
p p p
i i i p i i p
p p p
Q x x x Q x x x Q x x x
Q x x x Q x x
Q x Q λ
+ + + +
−
→ →
→ →
→ →
K K K
K K (2.2)
unde jx ∈Σ , ˆ QjQ ∈ şi ˆ FpQ ∈ . Tranziţiile corespund funcţie de tranziţie din
(2.3).
0 1 1 1 2 2
1 1 1
ˆ ˆ ˆ( , ) , ( , ) , ,ˆ ˆ ˆ ˆ( , ) , , ( , )i i i p p p
Q x Q Q x Q
Q x Q Q x Q
δ δ
δ δ+ + −
= =
= =
K
K(2.3)
Prin urmare, gramatica G include (printre altele) următoarele producţii:
0 1 1 1 2 2 1 1 1
1
ˆ ˆ ˆ ˆ ˆ ˆ ˆ, , , , , ,ˆ
i i i p p p
p p
Q x Q Q x Q Q x Q Q x Q
Q x+ + −
−
→ → → →
→
K K(2.4)
Ultima producţie este inclusă deoarece ˆpQ este o stare finală. Deci, şirul
1 2 px x xσ = K poate fi derivat în gramatica G astfel
0 1 1 1 2 2 1 2
1 2 1 1 1 2 1 1 1 2 1
ˆ ˆ ˆ
ˆ ˆi i
i i i p p p p
Q x Q x x Q x x x Q
x x x x Q x x x Q x x x x+ + − − −
⇒ ⇒ ⇒ ⇒
⇒ ⇒ ⇒
K K
K K K(2.5)
În toate derivările, cu excepţia ultimei, am folosit producţii de forma
1 1ˆ ˆ
i i iQ x Q+ +→ ; în ultima însă am folosit producţia 1ˆ
p pQ x− → . Inversa se
demonstrează în mod analog: Presupunem că derivarea unei propoziţii
1 2 px x xK în gramatica G este dată de (2.5). Aceasta implică că toate
producţiile din (2.4) sunt producţii în G, deci funcţia de tranziţie δ
satisface relaţiile (2.3) ceea ce implică, în final, că maşina M trece prin
secvenţa de configuraţii (2.3), 1 2 ( )px x x L M∈K . Prin urmare, suficienţa
teoreme 2.1. este demonstrată.
Ca exemplu, considerăm maşina M şi gramatica G din exemplul
2.4. Şirul abaabσ = aparţine limbajului ( )L M întrucât
0 1 2 1 0 0, , , , , ,Q abaab Q baab Q aab Q ab Q b Q λ→ → → → →
şi 0Q este o stare finală. Derivarea lui σ în gramatica G este atunci
3 7 9 5 2
0 1 2 1 0Q aQ abQ abaQ abaaQ abaab⇒ ⇒ ⇒ ⇒ ⇒ .
Numărul producţiei folosite este indicat deasupra săgeţilor.
Un mic comentariu merită să fie făcut asupra acceptării şirului vid
λ de o maşină cu stări finite M. Când un astfel de şir este prezentat
maşinii, ea porneşte din configuraţia 0( , )Q λ , unde 0Q este starea iniţială,
şi se opreşte fără să fi facă nici o singură mişcare. Deci, ( )L Mλ∈ dacă şi
numai dacă starea iniţială 0Q este o stare finală.
2.3. MAŞINI CU STĂRI FINITE NEDETERMINISTE
Demonstraţia necesităţii teoremei 2.1. este imediată. Dată fiind o
gramatică G, construim o maşină cu stări finite M care acceptă ( )L G ,
punând neterminalele să joace rolul stărilor şi incluzând tranziţia a
A B→
( ( , )A a Bδ = ) pentru fiecare producţie de forma A aB→ . Cu toate acestea,
după cum arată exemplul următor, ideea nu aduce rezultatul dorit. Fie G
gramatica
S aA→ A aB→ B b→
S bB→ A aS→ .
Dacă încercăm să construim maşina potrivit schemei indicate, apar două
dificultăţi. Mai întâi, ce ar trebui să fi ( , )B aδ ? Nu există o producţie de
forma B aX→ pentru nici un neterminal X. După cum vom vedea mai
târziu, acesta este doar un mic inconvenient care poate fi eliminat. O
problemă cu mult mai serioasă apare la producţiile A aB→ sau A aS→ . În
încercarea construirii maşinii M ne lovim de dilema definirii lui ( , )A aδ ,
de pildă, ce e de făcut când M se află în starea A şi citeşte simbolul a.
Producţia A aB→ implică ca următoarea stare ( , )A aδ să fie B, în timp ce
A aS→ sugerează să fie S. Aşadar, fragmentul diagramei de descriere a M
va arăta ca în figura 2.9.
L
a
i
d
n
Figura 2.9. Diagramă de tranziţie la ambiguitate.
a definirea maşinii cu stări finite în definiţia 2.1., s-a precizat că ( , )Q xδ
fost definită pentru fiecare stare Q în parte şi orice simbol de intrare x,
ar cunoscând Q şi x, ştim starea următoare, de exemplu, valoarea funcţie
e tranziţie ( , )Q xδ a fost unic definită. Maşina nu a fost lăsată să facă
ici o altă alegere. O modalitate de ieşire din acest impas este de a
extinde definiţia unei maşini cu stări finite, permiţând includerea
particularităţilor descrise mai sus. Astfel de dispozitive vor fi numite
automate finite nedeterministe (AFN) sau maşini cu stări finite
nedeterministe (MSFN). Se observă, că dată fiind o maşină de acest gen,
M, există un automat finit determinist obişnuit (definit ca în definiţia 2.1.)
care acceptă acelaşi limbaj ca M. În continuare vom descrie detaliat acest
concept.
Definiţia 2.3. O maşină cu stări finite nedeterministă (MSFN) se
compune din următoarele cinci obiecte:
1. O mulţime finită, nevidă 0 1Q { , , , }nQ Q Q= K de stări.
2. O mulţime finită, nevidă 1 2{ , , , }ka a aΣ = K de simboluri de
intrare admise (alfabetul).
3. O stare desemnată 0 QQ ∈ , numit stare iniţială.
4. O funcţie de tranziţie ( , )Q xδ , care nu trebuie definită pentru toţi
Q din Q şi x din Σ . Pentru acei Q şi x pentru care este definită,
( , )Q xδ desemnează o mulţime de una sau mai multe stări din Q.
Concret, dacă (Q)β este mulţimea tuturor submulţimilor din Q,
atunci funcţia de tranziţie este : Q (Q)δ β×Σ→ . Cu această
notaţie, ( , )Q xδ „nu e definită” înseamnă ( , )Q xδ =∅ (mulţimea
vidă). Funcţia δ se interpretează la fel ca în cazul determinist:
starea următoare. Diferenţa este doar, că admite mai multe
posibilităţi (sau nici una).
5. O mulţime nevidă F de stări. Elementele din F se numesc stări
acceptate sau finale.
Aceste maşini M vor fi notate 0{Q, , , , F}Q δΣ (ca maşinile
deterministe) şi se mai numesc automate finite nedeterministe (AFN).
Aşadar, totul e la fel ca în cazul determinist, cu excepţia definirii funcţie
de tranziţie δ . Mişcările unui MSFN sunt date în felul următor.
1. Fiind dat un şir 1 2 px x xσ = K de simboluri de intrare din Σ ,
configuraţia iniţială va fi 0 1 2, pQ x x xK , unde M este în starea
iniţială 0Q cu simbolul de intrare 1x .
2. Presupunem că la un moment dat, configuraţia M este
1, i i pQ x x x+ K . Dacă Q este una din valorile posibile ale lui
( , )iQ xδ (mai exact, ˆ ( , )iQ Q xδ∈ ) atunci M poate trece în
configuraţia 1ˆ , i pQ x x+ K . Deci, dacă M se află în starea Q şi
simbolul de intrare este x, M poate trece în orice stare din
( , )iQ xδ , dar nu în alta. Când ( , )iQ xδ =∅ nu se va face nici o
mişcare. Trecerea, dacă e posibilă, de la o configuraţie la alta, se
numeşte mişcare legală şi este notată prin
1 1ˆ, ,i i p i pQ x x x Q x x+ +→K K .
3. Maşina se opreşte dacă a citit întregul input (în configuraţia
,Q λ ) sau când ( , )iQ xδ =∅ ( ( , )iQ xδ nu conţine posibilităţi
pentru următoarea starea).
Exemplu 2.5. Fie M o MSFN după cum urmează. Mulţimea
stărilor Q are patru elemente: 0 1 2 3Q { , , , }Q Q Q Q= , alfabetul {1, 2, 3}Σ = ,
starea iniţială este 0Q şi mulţimea stărilor finale 2 3F { , ,}Q Q= .
Input curent
0 1 2
0Q 0 1{ , }Q Q 0{ }Q ∅
1Q ∅ 2{ }Q 0 3{ , }Q Q
2Q 2{ }Q 0 3{ , }Q Q ∅
S
t
ă
r
i 3Q 2{ }Q 1 3{ , }Q Q 3{ }Q
Figura 2.10. O funcţie de tranziţie nedeterministă δ .
F
d
i
i
Figura 2.11. O MSFN.
uncţia de tranziţie este dată de tabelul din figura 2.10., sau de diagrama
in figura 2.11. Astfel, dacă maşina se află în starea 1Q şi simbolul de
ntrare este 2, M poate trece în stările 0Q sau 3Q . Ca urmare, dat fiind un
nput σ , maşina M poate trece prin diferite secvenţe de mişcări. De
exemplu, pentru 01021σ = unele dintre mişcările posibile sunt
următoarele:
0 0 0 1 3 1, 01021 ,1021 , 021 , 21 ,1 , stopQ Q Q Q Q Q λ→ → → → → −
0 0 0 0, 01021 ,1021 , 021 , 21 stopQ Q Q Q→ → → −
0 1 2 2, 01021 ,1021 , 021 , 21 stopQ Q Q Q→ → → −
0 0 0 1 3 3, 01021 ,1021 , 021 , 21 ,1 , stopQ Q Q Q Q Q λ→ → → → → −
În prima secvenţă, input-ul este citit în întregime dar maşina se
opreşte într-o stare neacceptată; în a doua şi a treia secvenţă, M se opreşte
înainte ca şirul să fie citit în întregime; şi în a patra secvenţă, întregul şir
este citit iar ultima stare este o stare acceptată.
Dacă ,Q σ şi ˆ ˆ,Q σ sunt două configuraţii, astfel încât M poate
trece din ,Q σ în ˆ ˆ,Q σ printr-o secvenţă de mişcări admise, spunem că
ˆ ˆ,Q σ este derivabil din ,Q σ şi notăm aceasta
* ˆ ˆ, ,Q Qσ σ→ .
În exemplul 2.5. avem *
0 1, 01021 , 21Q Q→ şi *
0 3, 01021 ,Q Q λ→ . Putem
defini acum un limbaj generat (acceptat, recunoscut) de o maşină cu stări
finite nedeterministă.
Definiţia 2.4. Fie 0{Q, , , , F}M Q δ= Σ o MSFN. Spunem că un şir
1 2 px x xσ = K de elemente din Σ este acceptat de M dacă
*
0 1 2, ,pQ x x x Q λ→K
şi FQ∈ . Mulţimea şirurilor acceptate de M se notează ( )L M şi se
numeşte limbaj generat de M.
Observăm, că pentru ca un şir σ să fie acceptat de M, avem nevoie
doar de o secvenţă legală de mişcări din 0 ,Q σ în ,Q λ , unde Q este o
stare acceptată; nu toate secvenţele legale vor fi folosite aici. În exemplul
2.5. *
0 3, 01021 ,Q Q λ→ , deci 01021σ = este în ( )L M deoarece 3Q este o
stare acceptată. Chiar dacă maşina porneşte în configuraţia 0 , 01021Q , ea
poate ajunge în mai multe impasuri: *
0 0, 01021 , 21Q Q→ ,
*
0 2, 01021 , 21Q Q→ , etc.
Evident, că maşinile cu stări finite din definiţia 2.1. sunt cazuri
particulare ale maşinilor nedeterministe. Ele se caracterizate prin faptul că
pentru fiecare stare Q şi pentru fiecare input x mulţimea ( , )Q xδ este
formată dintr-o singură stare. Din acest motiv e de aşteptat ca clasa
limbajelor acceptate de maşini nedeterministe să fie mai mare decât clasa
acceptată de maşinile deterministe, de exemplu, să existe o MSFN M,
astfel încât pentru nici o maşină deterministă K să avem ( ) ( )L M L K= .
Surprinzător, acesta nu va fi cazul. Avem următoarea teoremă.
Teorema 2.2. Fie M o maşină cu stări finite nedeterministă. Atunci
există o maşină deterministă K astfel încât ( ) ( )L M L K= ; maşinile M şi K
acceptă acelaşi şir.
Demonstraţie. Luăm o maşină cu stări finite nedeterministă M, de
genul celei specificate în definiţia 2.3. Fie 0 1Q { , , , }nQ Q Q= K o mulţime de
stări din M, cu 0Q starea iniţială, 1 2{ , , , }ka a aΣ = K alfabetul, δ funcţia de
tranziţie şi F mulţimea stărilor acceptate. Maşina K se specifică astfel:
1. Alfabetul de intrare pentru K este Σ – acelaşi ca la M.
2. Stările din K vor fi toate submulţimile posibile din Q. De
exemplu, dacă M are trei stări – 0Q , 1Q şi 2Q – stările din K vor
fi 0 0{ }S Q= , 1 1{ }S Q= , 2 2{ }S Q= , 3 0 1{ , }S Q Q= , 4 0 2{ , }S Q Q= ,
5 1 2{ , }S Q Q= , 6 0 1 2{ , , }S Q Q Q= şi 7S =∅ – mulţimea vidă. (Se
include mulţimea vidă ca submulţime a fiecărei mulţimi.)
Astfel, dacă M are n stări maşina K va avea 2n stări:
0 1 2 2 1, , , , nS S S S
−K . Mulţimea stărilor din K se notează cu S.
3. K are starea iniţială 0 0{ }S Q= , unde 0Q este starea iniţială din M.
4. O stare SS ∈ va fi stare finală în K dacă şi numai dacă conţine o
stare finală FQ∈ din M. De exemplu, considerând M maşina din
exemplul 2.5., stările finale pentru K vor fi mulţimi care conţin
2Q sau 3Q (sau ambele). Acestea sunt 2{ }Q , 3{ }Q , 0 2{ , }Q Q ,
0 3{ , }Q Q , 1 2{ , }Q Q , 1 3{ , }Q Q , 2 3{ , }Q Q , 0 1 2{ , , }Q Q Q , 0 1 3{ , , }Q Q Q ,
0 2 3{ , , }Q Q Q , 1 2 3{ , , }Q Q Q şi 0 1 2 3{ , , , }Q Q Q Q – în număr de .
5. Funcţia de tranziţie ∆ pentru K este definită în felul următor.
Fie 1 2
{ , , , }pi i iS Q Q Q= K o stare din K şi x∈Σ . Valoarea ( , )S x∆
corespunde altei stare din K, de exemplu, o mulţime de Q-uri
definite după regula:
Dacă ( , )jQ Q xδ∈ pentru uni jQ din S, atunci ( , )Q S x∈∆
Formal avem
( , ) ( , )Q S
S x Q xδ∈
∆ = U (2.6)
Cu alte cuvinte, dacă pentru uni jQ din S maşina M poate trece la input-ul
x din starea jQ în Q, atunci ( , )Q S x∈∆ . O nedeterminare apare când S =∅
(mulţimea vidă, care este o stare din K). Formal, aceasta nu reprezintă o
problemă, deoarece formule (2.6) ne dă în acest caz ( , )x∆ ∅ =∅ oricare ar
fi x (o reuniune de mulţimi vide este vidă).
Astfel, maşina K e complet definită şi evident deterministă: Pentru
fiecare stare S din K şi fiecare simbol de intrare x, funcţia ( , )S x∆
defineşte în mod unic altă stare pentru K. Înainte de a trece la a demonstra
că ambele maşini acceptă acelaşi limbaj, să vedem, ca exemplu, cum
construim K.
Exemplu 2.6. Fie M maşina din exemplul 2.5. Maşina deterministă
corespunzătoare K are 16 ( 42= ) stări:
0 0{ }S Q= , 1 1{ }S Q= , 2 2{ }S Q= , 3 3{ }S Q= ,
4 0 1{ , }S Q Q= , 5 0 2{ , }S Q Q= , 6 0 3{ , }S Q Q= ,
7 1 2{ , }S Q Q= , 8 1 3{ , }S Q Q= , 9 2 3{ , }S Q Q= ,
10 0 1 2{ , , }S Q Q Q= , 11 0 1 3{ , , }S Q Q Q= , 12 0 2 3{ , , }S Q Q Q= ,
13 1 2 3{ , , }S Q Q Q= , 14 0 1 2 3{ , , , }S Q Q Q Q= şi 15S =∅ .
Starea iniţială este 0 0{ }S Q= şi stările acceptate sunt 2S , 3S , 5S , 6S , 7S , 8S ,
9S , 10S , 11S , 12S , 13S şi 14S , acei S care conţin 2Q şi/sau 3Q – stările finale
din M. Să calculăm unele valori ale funcţie de tranziţie ∆ .
Considerăm ca exemplu 5( ,1)S∆ . Deoarece 5 0 2{ , }S Q Q= şi 0 0( ,1) { }Q Qδ = ,
2 0 3( ,1) { , }Q Q Qδ = , atunci
5 0 2 0 0 3 0 3 6( ,1) ( ,1) ( ,1) { } { , } { , }S Q Q Q Q Q Q Q Sδ δ∆ = ∪ = ∪ = = , deci 5 6( ,1)S S∆ = .
Analog, pentru 7 1 2{ , }S Q Q= ,
7 1 2 2 2 2( , 0) ( , 0) ( , 0) { } { }S Q Q Q Q Sδ δ∆ = ∪ =∅∪ = = . De asemenea,
0 0 12( , 2) ( , 2)S Q Sδ∆ = =∅ = . Prin urmare 15 15( , )S x S∆ = pentru 0,1, 2x = .
Descrierea completă a funcţie de tranziţie ∆ este dată în tabelul din figura
2.12. Maşina K are propria diagramă de tranziţie, dar imaginea ei este
prea complexă. Aruncând o privire asupra tabelei funcţiei ∆ , se observă
că K are mai multe stări decât sunt necesare. De pildă, starea 7S nu poate
fi atinsă din starea iniţială 0S . De altfel, ea nu poate fi atinsă din nici o
stare. Aşadar, putem înlătura starea 7S iar maşina va accepta acelaşi şir.
Vom discuta, pe scurt, problema obţinerii unei MSF „pe cât posibil de
mică”. Ceea ce încercăm să arătăm acum este, că dată fiind o MSF
nedeterministă, există o MSF deterministă care acceptă exact acelaşi şir;
nu încercăm să găsim cea mai eficientă maşină de acest gen.
Input x
0 0{ }S Q= 4S 0S 15S
1 1{ }S Q= 15S 2S 6S
2 2{ }S Q= 2S 6S 15S
3 3{ }S Q= 2S 3S 3S
4 0 1{ , }S Q Q= 4S 5S 6S
5 0 2{ , }S Q Q= 10S 5S 15S
6 0 3{ , }S Q Q= 10S 11S 3S
7 1 2{ , }S Q Q= 2S 12S 6S
8 1 3{ , }S Q Q= 2S 13S 6S
9 2 3{ , }S Q Q= 2S 11S 3S
10 0 1 2{ , , }S Q Q Q= 10S 12S 6S
11 0 1 3{ , , }S Q Q Q= 10S 14S 6S
12 0 2 3{ , , }S Q Q Q= 10S 11S 3S
13 1 2 3{ , , }S Q Q Q= 2S 14S 6S
14 0 1 2 3{ , , , }S Q Q Q Q= 10S 14S 6S
S
t
ă
r
i
15S =∅ 15S 15S 15S
Figura 2.12. Tabela funcţie de tranziţie ∆ .
Ne întoarcem la a demonstra că ( ) ( )L K L M= . Presupunem că un şir
1 2, , , px x xσ = K este acceptat de M. Aceasta înseamnă că pentru o secvenţă
de stări 0 1 2ˆ ˆ ˆ, , , , pQ Q Q QK secvenţa de mişcări
11 2
0 0 1 2 1 1ˆ ˆ ˆ ˆ ˆ ˆ ˆpi xxx x
i i p pQ Q Q Q Q Q Q Q+
+ −= → → → → → → → →L L (2.7)
este legală, iar ˆpQ este o stare acceptată din M. Rezultă că pentru fiecare
0,1, 2, ..., 1i p= − , funcţia de tranziţie δ satisface
1 1ˆ ˆ( , ), 0,1, ..., 1i i iQ Q x i pδ+ +∈ = − (2.8)
Când şirul δ este introdus în maşina K, maşina execută următoarea
secvenţă de mişcări:
11 2
0 0 1 2 1 1ˆ ˆ ˆ ˆ ˆ ˆ ˆpi xxx x
i i p pS S S S S S S S+
+ −= → → → → → → → →L L (2.9)
Pentru 0i = în (2.8), 1Q este în 0 1ˆ( , )Q xδ , deoarece
1
0 1ˆ ˆ
x
Q Q→ este o tranziţie
legală în M, astfel 1Q este în 1 0 1ˆ ˆ( , )S S x= ∆ . Analog, cu 1i = , 2Q este în
1 2ˆ( , )Q xδ , deci 2 2 1 2
ˆ ˆ ˆ( , )Q S S x∈ = ∆ . Continuând în această manieră, observăm
că ˆjQ este în ˆ
jS oricare ar fi j, în particular, ˆ ˆp pQ S∈ . ˆ
pQ fiind o stare finală
în M (σ a fost acceptat de M), constatăm că ˆpS este o stare finală în K, σ
este acceptat de K.
Reciproc, presupunem că un şir 1 2, , , px x xσ = K este acceptat de K,
şi fie (2.9) secvenţa de mişcări făcute de K la input-ul σ . Pentru fiecare
1 1ˆ ˆQ S∈ mişcarea
1
0 1ˆ ˆ
x
Q Q→ este legală pentru maşina M ( 1S se compune din
acei Q pentru care 1
1ˆ
x
Q Q→ este mişcare legală în M). Analog, pentru
fiecare 2 2ˆ ˆQ S∈ există un 1Q în 1S astfel încât secvenţa de mişcări
1 2
0 1 2ˆ ˆ ˆ
x x
Q Q Q→ →
este legală în M. Alegem 1Q ca fiind starea pentru care tranziţia 1
1 2ˆ ˆ
x
Q Q→
este legală ( 1Q există deoarece 1 2 2ˆ ˆ( , )S x S∆ = ). În acelaşi mod arătăm, că
dacă 3 3ˆ ˆQ S∈ , atunci putem găsi 1 1
ˆ ˆQ S∈ şi 2 2ˆ ˆQ S∈ astfel încât
31 2
0 1 2 3ˆ ˆ ˆ ˆ
xx x
Q Q Q Q→ → → este o secvenţă legală de mişcări. Continuând în acest
fel, observăm că pentru fiecare ˆpQ şi ˆ
pS putem găsi 1 1ˆ ˆQ S∈ , 2 2
ˆ ˆQ S∈ , ...,
1 1ˆ ˆ
p pQ S− −∈ astfel încât (2.7) să fie o secvenţă legală de mişcări din M. Dacă
alegem acum ˆpQ din ˆ
pS , care este o stare acceptată din M, constatăm că
σ este acceptat de M, adică, face parte din limbajul ( )L M . Q.E.D.
Definiţia 2.5. Fie 1M şi 2M două MSF. Maşinile 1M şi 2M se
numesc echivalente dacă generează (acceptă) acelaşi limbaj,
1 2( ) ( )L M L M= .
Se observă imediat, din demonstraţia teoremei 2.2., că dată fiind o
maşină nedeterministă 1M , maşina deterministă corespunzătoare 2M este
destul de mare. Într-adevăr, dacă 1M are n stări, atunci construcţie cere de
la 2M 2n stări. Dacă 10n = , atunci 2M va avea 102 1024= stări. În
paragraful 2.5. vom arăta cum micşorăm 2M , de fapt cum să găsim cea
mai mică maşină echivalentă cu 2M . În unele cazuri, construirea lui 2M
poate fi cu mult simplificată. Ne reamintim că maşina 0{Q, , , , F}M Q δ= Σ
va eşua la determinism din două motive:
1. ( , )Q xδ =∅ pentru QQ∈ şi x∈Σ (dacă M se află în starea Q
şi simbolul de intrare este x, următoarea stare e nedefinită).
2. ( , )Q xδ conţine mai mult de o stare (pentru unii Q şi x).
Natura celor două cazuri diferă; maşina M nu este „chiar” nedeterministă,
problema constă în faptul că se poate „bloca” într-un punct mort. Din
acest motiv, unii autori nu consideră astfel de maşini nedeterministe. În
cazuri în care apare 1 şi 2 nu (atunci când ( , )Q xδ este întotdeauna goală
sau conţine o singură stare) construirea unei maşini deterministe
echivalente poate fi cu mult simplificată.
Teorema 2.3. Fie 0{Q, , , , F}M Q δ= Σ o maşină cu stări finite
nedeterministă astfel încât pentru fiecare QQ∈ şi x∈Σ mulţimea ( , )Q xδ
este vidă sau conţine un singur element. Fie K o maşină obţinută din M
prin adăugarea unei stări noi D, şi a cărei funcţie de tranziţie ∆ este
definită după cum urmează:
( , ) dacă ( , )( , )
{ } dacă ( , )Q x Q x
Q xD Q xδ δ
δ≠ ∅
∆ = =∅ ( , ) { } pentru toţiD x D x∆ = ∈Σ
Stările finale şi iniţiale din K sun aceleaşi ca şi în M – în particular D nu
este o stare acceptată. Atunci K este o maşină deterministă şi echivalentă
cu M.
Starea D introdusă mai sus are înţelesul de „capcană” sau stare
„moartă”. Ideea din spatele teoremei 2.3. este evidentă: Dacă maşina M se
blochează într-o stare oarecare, şirul σ citit nu poate fi acceptat. Totuşi se
trimite maşina în acea stare „moartă”.
Demonstraţie. Faptul că K e deterministă este evident: Pentru
fiecare stare { }Q Q D∈ ∪ şi x∈Σ mulţimea ( , )Q x∆ conţine numai o
singură stare. Dacă un şir 1 2, , , px x xσ = K este acceptat de M, atunci
secvenţa de mişcări din K, la input-ul σ , este aceeaşi ca secvenţa de
mişcări din M cu acelaşi input – singura posibilitate ca mişcările să difere
este când M se blochează într-o configuraţie
1, ( , )i i p iQ x x x Q xδ+ = ∅K (2.10)
Deoarece M acceptă σ , aceasta nu va avea loc. Reciproc, dacă M nu
acceptă σ , atunci ori M trece din configuraţia 0 ,Q σ în ,Q λ unde Q nu
e stare acceptată, caz în care K face acelaşi lucru, ori M se blochează în
configuraţia (2.10). În acest caz, K continuă prin a trece în starea D şi
rămâne aici până când s-a citit restul şirului. Cum D nu este o stare
acceptată, K nu acceptă pe σ . Q.E.D.
Exemplu 2.7. Considerăm maşina M a cărei diagramă de tranziţie
este dată în figura 2.13. Evident, M satisface condiţiile teoremei 2.3.,
maşina K echivalentă cu M este dată de diagrama figurii 2.14.
Figura 2.13. Funcţie de tranziţie incompletă.
Figura 2.14. Completarea funcţiei de tranziţie.
2.4. GRAMATICI REGULARE ŞI MAŞINI CU STĂRI FINITE
În această parte completăm demonstraţia teoremei 2.1. arătând că,
dată fiind o gramatică regulată G, există o maşină cu stări finite
deterministă M astfel încât ( ) ( )L M L G= . Vom demonstra doar pentru
gramaticile liniare la dreapta (producţiile sunt de forma S λ→ , A aB→
sau A a→ ); cazul gramaticilor liniare la stânga este simplu şi va fi lăsat
ca exerciţiu. În contextul teoremei 2.2., este suficient de arătat că dată
fiind o gramatică liniară la dreapta, există o maşină nedeterministă M
astfel încât ( ) ( )L M L G= .
Teorema 2.4. Fie G o gramatică liniară la dreapta. Atunci există o
maşină cu stări finite nedeterministă M astfel încât ( ) ( )L G L M= .
Demonstraţie. Fie G cu alfabetul 1 2{ , , , }ka a aΣ = K , mulţimea de
neterminale { , , , }N S A B= K , S simbolul de start şi P mulţimea
producţiilor. Alfabetul de intrare pentru M va fi tot Σ , stările din M vor fi
neterminalele , , ,S A B K , plus o stare X, diferită de celelalte neterminale.
Starea iniţială din M este S. Stările acceptate din M sunt X şi, dacă S λ→
este o producţie în G, starea S. Funcţia de tranziţie δ din M este definită
prin următoarele reguli:
1. Pentru fiecare producţie de forma A aB→ din G se include B în
( , )A aδ , de exemplu, se include tranziţia a
A B→ în diagrama de
tranziţie.
2. Pentru fiecare producţie de forma A a→ se include starea X în
( , )A aδ , de exemplu, se include tranziţia a
A X→ în diagrama de
tranziţie.
În general, maşina rezultată fa fi nedeterministă. Trebuie să arătăm că
şirurile acceptate de M sunt chiar acelea ce sunt derivabile în G. Fie
1 2 nx x xσ = K un şir acceptat de M. Prin definiţie există o secvenţă legală de
mişcări
31 2
1 2 3 1
nx xx x
n nS Z Z Z Z Z += → → → → →L (2.11)
unde 1nZ + este stare acceptată şi 1nZ X+ = sau (eventual) 1nZ S+ = . Pentru
fiecare i n< tranziţia 1
ix
i iZ Z +→ este legală, ceea ce implică că
1 ( , )i i iZ Z xδ+ ∈ , astfel încât 1i i iZ x Z +→ este o producţie în G. Considerăm
acum ultima tranziţie 1
nx
n nZ Z +→ . Dacă 1nZ X+ = , atunci G are producţii de
forma n nZ x→ ; dacă 1nZ S+ = , atunci G trebuie să aibă producţiile n nZ x S→
şi S λ→ . Astfel, secvenţa de derivări pentru σ în G este dată ori de
(2.12) ori de (2.13):
1 1 2 1 2 3 1 2 1 1 2 1n n n nS Z x Z x x Z x x x Z x x x x− −= ⇒ ⇒ ⇒ ⇒ ⇒L K K (2.12)
1 1 2 1 2 3 1 2 1 1 2 1 1 2n n n n nS Z x Z x x Z x x x Z x x x x S x x x− −= ⇒ ⇒ ⇒ ⇒ ⇒ ⇒L K K K (2.13)
În ambele cazuri, σ este derivabil în G. Şi reciproca este adevărată.
Presupunem că σ este în ( )L G ; derivarea lui trebuie să fie de forma
(2.12) sau (2.13). În ambele cazuri (2.11) este o secvenţă legală de
mişcări din M. Ceva atenţie trebuie acordată situaţiei când σ λ= este şirul
vid. Dacă S λ→ este o producţie din G atunci evident ( )L Gλ∈ . În acest
caz S este tot o stare acceptată, astfel încât, dacă λ este introdus în M,
configuraţia iniţială a maşinii va fi ,S λ şi se opreşte fără să facă o
singură mişcare. S fiind o stare acceptată, M acceptă λ , ( )L Mλ∈ . Q.E.D.
Exemplu 2.8. Considerăm gramatica
| |S aA aB λ→
|A aA b→
|B bS b→
Diagrama maşinii nedeterministe M, astfel încât ( ) ( )L G L M= , este dată în
figura 2.15. S λ→ fiind o producţie, starea S e acceptată. Tranziţia b
A X→
este rezultatul producţiei A b→ ; b
B S→ provine din producţia B bS→ ;b
A A→ din A aA→ , etc.
Figura 2.15. Maşină cu stări finite nedeterministă care recunoaşte un
limbaj.
Pentru a construi o maşină deterministă K astfel încât ( ) ( )L K L G= ,
ne putem folosi de metoda utilizată în demonstraţia teoremei 2.2. Maşina
rezultată K are 16 stări şi funcţia de tranziţie dată de tabela din figura
2.16. Un număr mare de stări nu poate fi atins din starea iniţială 0Q . De
exemplu, 4Q nu poate fi atins din nici o stare, deci poate fi eliminată.
Desigur, maşina obţinută nu este cea mai mică posibilă. Ideea teoremei
2.2. este că o astfel de maşină poate fi construită. Vom discuta problema
găsirii celei mai mici maşini în paragraful următor. Starea iniţială în K
este 0Q iar stările acceptate sunt 0Q , 3Q , 4Q , 5Q , 6Q , 8Q , 9Q , 10Q , 11Q ,
12Q , 13Q şi 14Q (acei Q care conţin S sau X).
Input x
a b
0Q { }S= 7Q 15Q
1Q { }A= 1Q 3Q
2Q { }B= 15Q 6Q
3Q { }X= 15Q 15Q
4Q { , }S A= 7Q 3Q
5Q { , }S B= 7Q 6Q
6Q { , }S X= 7Q 15Q
7Q { , }A B= 1Q 2Q
8Q { , }A X= 1Q 3Q
9Q { , }B X= 7Q 6Q
10Q { , , }S A B= 7Q 6Q
11 , , }Q { A XS= 7Q 3Q
12Q { , , }S B X= 7Q 6Q
13Q { , , }A B X= 1Q 6Q
14Q { , , , }S A B X= 7Q 6Q
S
t
ă
r
i
15Q =∅ 15Q 15Q
Figura 2.16. Funcţia de tranziţie a maşinii K.
Considerăm acum, de exemplu, derivarea
S aB abS abaA abaaA abaab⇒ ⇒ ⇒ ⇒ ⇒
Mişcările maşinii nedeterministe K corespunzătoare acestei derivări sunt
, , , , , , ,S abaab B baab S abaab S aab A ab A b X λ→ → → → → → .
Pe de altă parte, maşina deterministă K va executa secvenţa de mişcări
0 7 0 6 7 1 3, , , , , , ,Q abaab Q baab Q abaab Q aab Q ab Q b Q λ→ → → → → →
.
2.5. MINIMIZARE
Exemplele din paragrafele anterioare ne arată că chiar gramatici
simple conduc la maşini mari. Ar fi de mare ajutor o metodă de reducere
a mărimii maşinilor, dacă e posibil. Considerăm, de exemplu, MSF 1M
din figura 2.17. Stările 3Q şi 4Q pot fi combinate într-o singură stare T,
fără a schimba limbajul generat de 1M . Rezultă o maşină echivalentă 2M
ilustrată în figura 2.18.
Figura 2.17. O maşină cu stări finite cu prea multe stări.
Orice input σ acceptat de 1M este de asemenea acceptat de 2M şi invers.
Maşina 2M poate fi redusă mai mult combinând stările 1Q şi 2Q într-o
singură stare R. Se obţine o MSF 3M ca în figura 2.19. Descrierea
limbajului generat de 2M (deci şi de 1M ) este acum evidentă: 3( )L M se
compune din toate şirurile de lungime patru, formate din simboluri de 0 şi
1, terminate în 0.
Figura 2.18. Eliminare de stări.
Figura 2.19. Maşină cu stări finite minimală.
Există un algoritm, care, dacă dată fiind o maşină cu stări finite
deterministă 1M , va produce cea mai mică maşină cu stări finite 2M astfel
încât 1 2( ) ( )L M L M= . Dedicăm acest paragraf descrierii acestui algoritm.
Începem cu a arăta cum se elimină dintr-o maşină aşa numitele stări
inaccesibile.
Definiţia 2.6. Fie M o maşină cu stări finite. Spunem că o stare Q
din M este inaccesibilă dacă nu există un şir de intrare σ astfel încât*
0 , ,Q Qσ λ→ . Unde 0Q este starea iniţială din M.
Cu alte cuvinte, o stare Q din M este inaccesibilă dacă, începând cu
stare iniţială 0Q , maşina nu va ajunge niciodată în starea Q, indiferent de
input. De exemplu, stare 1Q a maşinii din figura 2.20. este inaccesibilă.
Figura 2.20. O maşină cu stări finite având o stare inaccesibilă.
Evident vom avea:
Teorema 2.5. Fie 1M o maşină cu stări finite şi fie 2M o maşină
obţinută din 1M prin eliminarea stărilor inaccesibile. Atunci
1 2( ) ( )L M L M= .
Dată fiind o maşină M, toate stările sale inaccesibile pot fi găsite cu
următorul algoritm.
Algoritm 2.1. Stări inaccesibile ale unei maşini cu stări finite.
Input: O maşină cu stări finite 0{Q, , , , F}M Q δ= Σ .
Output: O mulţime ϑ de stări inaccesibile.
Mai întâi, mulţimea de stări accesibile A se construieşte astfel.
Formăm o secvenţă {A }n de mulţimi de stări din M conform regulilor:
1. 0 0A { }Q= , 0A se compune dintr-o singură stare 0Q – starea
iniţială din M.
2. Se presupunem kA deja construit pentru 0k ≥ . Mulţimea
k+1A se formează prin adăugarea la kA a stărilor din M
accesibile din kA printr-o singură mişcare,
k k kˆ ˆA A { : Pentru din A şi din , ( , ) }Q Q x Q x Qδ= ∪ Σ = .
3. Dacă k k+1A A= , de exemplu, când nu sunt adăugate stări
noi la kA , ne oprim şi punem kA A= . În caz contrar ne
întoarcem la pasul 2.
Fiind un număr finit n de stări din M, acest proces se va termina în cel
mult 1n − iteraţii. Mulţimea de stări inaccesibile ϑ se obţine din Q prin
eliminarea elementelor din A, Q \ Aϑ = (sunt eliminate din A elementele
mulţimii Q).
Figura 2.21. Eliminarea stărilor inaccesibile.
Exemplu 2.9. Fie M maşina dată prin diagrama de tranziţie din
figura 2.21. Atunci avem:
0 0A { }Q= – prin definiţie
1 0 1 2 0 1 2A { } { , } { , , }Q Q Q Q Q Q= ∪ = , cu 0 1( , 0)Q Qδ = şi 0 2( ,1)Q Qδ =
2 1 4 0 1 3 4A A { } { , , , }Q Q Q Q Q= ∪ = cu 2 4( , 0)Q Qδ =
3 2A A= – din 2A nu se pot atinge stări noi
Astfel 2 0 1 2 3A A { , , , }Q Q Q Q= = şi 3{ }Qϑ = este mulţime stărilor inaccesibile.
Starea 3Q poate fi eliminată din M.
Menţionăm că acest algoritm se poate aplica şi maşinilor
nedeterministe. De pildă, maşina din exemplul 2.8. are doar şase stări
accesibile. Verificarea o lăsăm ca exerciţiu. În continuare vom presupune
că fiecare maşină cu stări finite nu are stări inaccesibile şi ne concentrăm
asupra eliminării stărilor „structural redundante”. Procedeul folosit în
acest scop se bazează pe conceptul de congruenţă.
Definiţia 2.7. Fie 0{Q, , , , F}M Q δ= Σ o maşină deterministă cu stări
finite şi 0k ≥ un întreg. Numim două stări Q şi Q k-congruente dacă
următoarele sunt adevărate:
Fie σ un şir de intrare de lungime cel mult k şi presupunem că*
, ,Q Pσ λ→ , *ˆ ˆ, ,Q Pσ λ→ descriu mişcările din M cu input-ul
σ , începând cu stările Q şi Q . Atunci sau P şi P sunt acceptate
împreună, sau ele nu sunt acceptate împreună.
Dacă Q şi Q sunt k-congruente, vom nota acesta prin ˆkQ Q≡ . Dacă Q şi
Q sunt k-congruente pentru toţi 0,1,k = K , spunem că Q şi Q sunt
congruente şi notăm ˆQ Q≡ .
Înţelesul k-congruenţei este următorul. Presupunem că τ este şirul
de testat din ( )L M . Pornim maşina în configuraţia 0 ,Q τ ; M îşi continuă
mişcările până când ajunge în configuraţia ,Q σ , unde σ este un şir de
lungime cel mult k. Dacă Q şi Q sunt k-congruente putem schimba starea
din Q în Q şi continuăm de aici (cu input-ul σ ), fără ca să se schimbe
rezultatul final: Dacă se porneşte cu configuraţia ,Q σ , maşina se va
opri într-o stare acceptată, acest lucru este valabil şi când maşina a pornit
din configuraţia ˆ ,Q σ . Presupunem că Q şi Q sunt k-congruente pentru
toţi 0,1,k = K . Atunci putem combina Q şi Q într-o singură stare – nu va
avea efect asupra mulţimii de şirului acceptate de M. Astfel, pentru a
minimiza o maşină cu stări finite M, trebuie să determinăm stările
congruente între ele. Din definiţie avem
1. Dacă 1 2ˆ
kQ Q≡ atunci 2 1ˆ
kQ Q≡ . (simetric)
2. Pentru orice stare Q avem ˆkQ Q≡ . (reflexiv)
3. Dacă 1 2ˆ
kQ Q≡ şi 2 3ˆ
kQ Q≡ atunci 1 3ˆ
kQ Q≡ . (tranzitiv)
Deci, relaţia k≡ fiind simetrică, reflexivă şi tranzitivă, ea este o relaţie de
echivalenţă. Evident expresiile 1, 2 şi 3 de mai sus, vor rămâne adevărate
chiar dacă k≡ se înlocuieşte cu ≡ , astfel, congruenţa ≡ este o relaţie de
echivalenţă pe stările din M. Problema minimizării unei maşini M constă,
în esenţă, în împărţirea stărilor din M în clase echivalente; oricare două
stări dintr-o clasă vor fi echivalente între ele, iar oricare două stări din
clase diferite nu vor fi echivalente între ele. Maşina minimizată va avea
ca stări aceste clase de echivalenţă. Se observă că acest procedeu
furnizează cea mai mic posibilă maşină echivalentă cu cea originală,
adică maşina cu cele mei puţine stări.
Înainte de a da un algoritm, avem nevoie de două leme.
Lema 2.1. Dacă două stări ale unei maşini sunt ( 1)k + -congruente,
ele sunt şi k-congruente.
Demonstraţia rezultă imediat din definiţie.
Lema 2.2. Fie 0{Q, , , , F}M Q δ= Σ o maşină cu stări finite. Fie 0k ≥
un întreg fixat şi 1 2, , , nKG G G partiţia stărilor din M în clase de echivalenţe:
Două stări din fiecare clasă sunt k-congruente între ele şi două stări din
clase diferite nu sunt k-congruente între ele. Fie G una din aceste clase şi
1 2, , , mQ Q QK stările din G . Pentru fiecare simbol x∈Σ şi Q∈G , fie
( , )kh Q x clasa iG cu ( , )Q xδ . Atunci stările Q şi Q din G sunt
( 1)k + -congruente dacă şi numai dacă
ˆ( , ) ( , ) pentru fiecare k kh Q x h Q x x= ∈Σ (2.14)
Demonstraţie. Presupunem Q şi Q sunt două stări din aceeaşi
clasă G şi mai presupunem că (2.14) este adevărat. Vrem să arătăm că Q
şi Q sunt ( 1)k + -congruente, adică, dacă σ este un şir de lungime maximă
1k + , cu *
, ,Q Pσ λ→ şi *ˆ ˆ, ,Q Pσ λ→ , atunci ori P şi P sunt stări
acceptate, ori amândouă nu sunt stări acceptate. Dacă şirul σ este de
lungime maximă k, ne oprim, fiindcă conform ipotezei, Q şi Q sunt în
aceeaşi clasă G de k≡ -echivalenţă, deci, ˆkQ Q≡ . Presupunem atunci că σ
are lungimea 1k + , de exemplu, xσ τ= , unde x∈Σ şi τ este de lungime k.
Dar atunci
*
1, , , ,Q Q x Q Pσ τ τ λ= → →
şi
*
1ˆ ˆ ˆ ˆ, , , ,Q Q x Q Pσ τ τ λ= → →
şi ambii 1Q şi 1Q aparţin aceleaşi clase 'G (deoarece (2.14) e valabilă, deci' ˆ( , ) ( , )k kh Q x h Q x= =G ). Astfel 1 1
ˆkQ Q≡ şi τ având lungimea k, observăm că
P şi P sunt amândoi acceptaţi sau neacceptaţi.
Reciproc, presupunem Q şi Q sunt două stări ( 1)k + -congruente;
vrem să arătăm că (2.14) este adevărată. Într-adevăr, dacăˆ( , ) ( , )k kh Q x h Q x≠ pentru x∈Σ , atunci 1( , ) ( , )kQ x Q h Q xδ = ∈ şi
1ˆ ˆ ˆ( , ) ( , )kQ x Q h Q xδ = ∈ , deci 1Q şi 1Q nu sunt k-congruente. Aceasta implică,
că pentru un şir oarecare σ , de lungime cel mult k, configuraţiile 1,Q σ
şi 1ˆ ,Q σ se vor „termina” diferit: una într-o stare acceptată iar cealaltă
într-una neacceptată. Acelaşi lucra este atunci adevărat şi pentru
configuraţiile ,Q xσ şi ˆ ,Q xσ . Pe de altă parte, lungimea lui xσ este
1k + , ceea ce contrazice ipoteza că Q şi Q sunt ( 1)k + -congruente. Q.E.D.
Când 0k = împărţirea stărilor în clase 0-congruente este simplă. Se
observă că două stări sunt 0-congruente dacă şi numai dacă fie că sunt
amândouă acceptate sau fie că amândouă sunt neacceptate. Astfel, pentru
0k = , există două clase de echivalenţă: (0)1G – toate stările neacceptate şi
(0)2G – toate stările acceptate. Algoritmul de împărţire a stărilor în clase de
≡ - echivalenţe va opera în felul următor. Mai întâi se împart stările din M
în două grupuri (0)1G şi (0)
2G – clasele de echivalenţă pentru relaţia 0≡ (am
arătat adineauri ce sunt ele). Folosind lema 2.2., fiecare dintre aceştia sunt
împărţite în alte subgrupuri; partiţia rezultată formează clasa de
echivalenţă pentru 1≡ . Operaţia se repetă, până nu mai apar subdiviziuni.
Descrierea formală exactă a algoritmului este următoarea.
Algoritm 2.2. Maşină cu stări finite minimală.
Input: O maşină cu stări finite 0{Q, , , , F}M Q δ= Σ .
Output: O maşină cu stări finite K, cu cele mai puţine stări posibile,
astfel încât ( ) ( )L K L M= .
I. Construire de stări din K. Stările din K vor fi clase de echivalenţă
a stărilor din M sub relaţia de echivalenţă ≡ . Aşadar, stările din K sunt
mulţimile de stări 1 2, , , rKG G G din M astfel încât 1Q , 2Q să fie membrii din
acelaşi G dacă şi numai dacă 1 2Q Q≡ . Aceste clase se construiesc în felul
următor.
1. Fie (0)1G mulţimea stărilor neacceptate şi (0)
2G mulţimea
tuturor stărilor acceptate din M.
2. Presupunem că mulţimile din M au fost împărţite în clase
de echivalenţe
(k) (k) (k)1 2, , ,
kmKG G G (2.15)
cu relaţia k≡ . Pentru fiecare stare Q şi x∈Σ fie ( , )kh Q x clasa(k)
iG care conţine ( , )Q xδ . Se împarte fiecare mulţime (k)iG din
(2.15) astfel. Două stări Q şi Q din (k)iG vor aparţine aceleaşi
clase dacă şi numai dacă ˆ( , ) ( , )k kh Q x h Q x= , pentru fiecare x din
Σ . Fie partiţia de stări din M obţinută
1
(k+1) (k+1) (k+1)1 2, , ,
km +KG G G (2.16)
3. Dacă mulţimile din (2.16) sunt identice cu cele din (2.15), ne
oprim. Am obţinut partiţionarea în clase de echivalenţă. Dacă în
(2.16) sunt mai multe clase decât în (2.15), ne întoarcem la
pasul 2.
II. K are acelaşi alfabetul de intrare ca şi M, adică mulţimea Σ .
III. Starea iniţială din K este clasa de echivalenţă care conţine
starea iniţială 0Q din M.
IV. Funcţia de tranziţie se defineşte pentru K astfel: Fie
1 2 r, , ,KG G G (2.17)
stările din K. Există clase de echivalenţe pentru acel k pentru care clasele
de echivalenţă din (2.16) sunt identice cu cele din (2.15). Din construcţia
părţii I rezultă că dacă Q şi Q sunt în aceeaşi iG , atunci ˆ( , ) ( , )k kh Q x h Q x= ,
oricare ar fi x∈Σ . Astfel funcţia
( , ) ( , ) pentru oricare kx h Q x Q∆ = ∈G G
este bine definită, independent de Q. (Observăm că ( , )x∆ G este o clasă de
echivalenţă, una din G -uri, deoarece ( , )kh Q x este clasa de echivalenţă
care conţine ( , )Q xδ .) Luăm funcţia ∆ ca funcţie de tranziţie pentru K.
V. O stare G este stare acceptată dacă şi numai dacă se compune
din stări acceptate din M.
Vom ilustra algoritmul 2.2. în exemplul următor.
Exemplu 2.10. Fie M maşina cu stări finite dată de diagrama din
figura 2.22. Clasa (0)1G (a stărilor neacceptate) este
0 1 2 3 4 6 7 9{ , , , , , , , }Q Q Q Q Q Q Q Q . Clasa (tuturor stărilor acceptate) (0)2G este
5 8{ , }Q Q . Următoarea subdivizare se obţine cu ajutorul funcţiei
(0)0 ( , ) clasa care conţine ( , )ih Q x Q xδ= G .
Figura 2.22. Minimizarea unei maşini cu stări finite.
Astfel, pentru 1k = clasa (0)1G se împarte în două subclase
(1)1 0 2{ , }Q Q=G şi (1)
2 1 3 4 6 7 9{ , , , , , }Q Q Q Q Q Q=G .
Clasa (0)2G nu se împarte ( 5Q şi 8Q produc rânduri identice) şi devine (1)
3G .
Continuarea împărţirii este redată în de tabelul din figura 2.24. Am omis
unele G -uri şi Q-uri, reţinând doar indicii relevanţi. ( (3)3G este reprezentat
ca 3 şi 5Q ca 5.) Partea superioară lui Pas #1 al tabelei din figura 2.24.
este identică cu tabelul figurii 2.23. În Pas 4# ( 3k = ) nu sunt introduse
subclase noi, astfel, clasele de echivalenţă din M, deci stările din K, sunt
1 0{ }Q=G , 2 2{ }Q=G , 3 1{ }Q=G , 4 3 4 6 7 9{ , , , , }Q Q Q Q Q=G , 5 5 8{ , }Q Q=G .
Starea iniţială din K este 1G şi starea finală este 5G . Funcţia de tranziţie ∆
este dată de funcţia 3h în tabelul din figura 2.24. De exemplu, 4 4( , )a∆ =G G
deoarece 3 3 3 4 3 6 3 7 3 9 4( , ) ( , ) ( , ) ( , ) ( , )h Q a h Q a h Q a h Q a h Q a= = = = = G . În exact
acelaşi mod se obţine 5 4( , )b∆ =G G cu 3 5 3 8 4( , ) ( , )h Q b h Q b= = G . În final,
diagrama de tranziţie pentru K este dată în figura 2.25.
0h(0)G Q
0 ( , )h Q a 0 ( , )h Q b
0Q (0)1G (0)
2G
1Q (0)1G (0)
1G
2Q (0)1G (0)
1G
3Q (0)1G (0)
1G
4Q (0)1G (0)
1G
6Q (0)1G (0)
1G
7Q (0)1G (0)
1G
(0)1G
9Q (0)1G (0)
1G
5Q (0)1G (0)
1G(0)
2G
8Q (0)1G (0)
1G
Figura 2.23. Primul pas din algoritmul 2.2.
Rândurile pentru 0Q şi 1Q sunt distincte, deci 0Q şi 1Q vor aparţine
diferitor clase (1)G . Pentru 2Q şi 3Q ele sunt identice, deci aparţin aceleaşi
clase (1)G .
0h 1h 2h 3h(0)G
Q a b(1)G
Q a b(2)G
Q a b(3)G
Q a b
0 1 2 0 2 3 0 2 4 1 0 3 5
1 1 11
2 2 31
2 3 4 2 2 4 5
2 1 2 1 2 1 2 1 3 1 3 1 4 2
3 1 1 3 2 2 3 3 3 3 4 4
4 1 1 4 2 2 4 3 3 4 4 4
6 1 1 6 2 2 6 3 3 6 4 4
7 1 1 7 2 2 7 3 3 7 4 4
1
9 1 1
2
9 2 2
3
9 3 3
4
9 4 4
5 1 1 5 2 2 5 3 3 5 4 42
8 1 13
8 2 24
8 3 35
8 4 4
Pas #1
0k =
Pas #2
1k =
Pas #3
2k =
Pas #4
3k =
Figura 2.24. Algoritmul 2.2. complet.
Figura 2.25. Maşină minimizată.
Încheiem acest paragraf prin a arăta că algoritmul 2.2. funcţionează
corect.
Teorema 2.6. Fie M şi K maşinile cu stări finite deterministe din
algoritmul 2.2. Atunci ( ) ( )L K L M= . Mai mult, dacă 1K este o MSFD
astfel încât 1( ) ( )L K L M= atunci numărul de stări din 1K este cel puţin egal
cu numărul de stări din K.
Demonstraţie. Fie Q şi Q două stări din M şi fie G şi G două stări
din K astfel încât Q∈G şi ˆ ˆQ∈G . Din construcţia lui K rezultă că pentru
oricare x∈Σ
ˆ ˆDacă ( , ) atunci ( , )Q x Q xδ = ∆ =G G (2.18)
Fie acum 1 2 px x xσ = K un şir acceptat de M. Secvenţa de mişcări efectuate
de M la input-ul σ este
31 2
1 20
p
p
xxx x
i i iQ Q Q Q→ → → →L (2.19)
unde pi
Q este stare acceptată în M. Fie 1 2, , ,
pi i iKG G G stările din K astfel
încât j ji iQ ∈G . Din (2.18) rezultă că secvenţa de mişcări din K este
31 2
1 20
p
p
xxx x
i i i→ → → →LG G G G (2.20)
Deoarece p pi iQ ∈G , starea
piG este stare acceptată în K, deci ( )L Kσ ∈ .
Reciproc, dacă σ nu este în ( )L M atunci starea pi
Q din (2.19) nu este
stare finală în M, şi din nou, deoarece p pi iQ ∈G , starea
piG nu este stare
finală în K, deci ( ).L Kσ ∉ Ca urmare ( ) ( )L K L M= .
Pentru a arăta că maşina K are minimul de stări, procedăm în felul
următor. Fie 1K o maşină cu stări finite deterministă cu mai puţine stări
decât K. Vom arăta că 1( ) ( ) ( )L K L M L K≠ = . Toate stările din M fiind
accesibile, şi stările din K vor fi de asemenea toate accesibile. Astfel,
pentru fiecare G din K există un şir ( )σ σ= G astfel încât *
0 , ,σ λ→G G .
Fie 0P starea iniţială din 1K , şi considerăm mişcările din 1K la input-ul
( )σ G pentru toate stările posibile G din K. Pentru fiecare astfel de G
maşină 1K se va opri într-o configuraţie ( ),P λG pentru o stare oarecare
( )P G din 1K . Deoarece 1K are mai puţine stări decât K, vor exista două
stări diferite din K, fie ele 'G şi ''G , astfel încât ' ''( ) ( )P P=G G . Cu alte
cuvinte, există două şiruri diferite ' '( )σ σ= G şi '' ''( )σ σ= G astfel încât
1. La input-ul 'σ şi ''σ maşina 1K se mişcă din 0P în aceeaşi stare
P.
2. La input-ul 'σ şi ''σ maşina K se mişcă din 0G în două stări
diferite 'G şi ''G .
Fie 'Q o stare din M conţinută în 'G şi fie ''Q o stare din M conţinută în''G . Având ' ''≠G G , stările 'Q şi ''Q nu sunt congruente. Deci pentru un
input τ , maşina M va trece din 'Q în Q şi din ''Q în Q unde una din
stările Q şi Q este acceptată iar cealaltă nu. Aceasta implică că unul din
şirurile 'σ τ şi ''σ τ este în ( )L M iar celălalt nu. Să vedem ce se întâmplă
când aceste şiruri sunt introduse în maşina 1K . La input-ul 'σ τ maşina 1K
trece din configuraţia '0 ,P σ τ în ,P τ . La fel, cu input-ul ''σ τ maşina 1K
trece din ''0 ,P σ τ în aceeaşi configuraţie ,P τ iar apoi continuă până se
epuizează şirul τ . Aşadar, 1K trebuie să accepte fie ambele şiruri 'σ τ şi''σ τ fie să le respingă pe amândouă. Ca urmare 1( ) ( )L K L M≠ , deoarece
prin construcţie, maşina ( )L M acceptă doar unul dintre aceste şiruri.
Q.E.D.
2.6. MAŞINI CU STĂRI FINITE BIDIRECŢIONALE
Există o variantă modificată a conceptului de maşină cu stări finite,
după cum vom vedea în continuare. Ne reamintim, că la definirea
automatelor finite a fost precizat faptul, că dacă maşina citeşte un simbol
x şi se află într-o stare Q, ea va trece în starea ( , )Q xδ şi va deplasează
capul de citire cu un simbol spre dreapta. Presupunem acum că permitem
capului de citire să efectueze mişcări la dreapta şi la stânga sau deloc.
Astfel, dacă maşina se află în starea Q şi simbolul de intrare este x, ea
poate efectua următoarele:
1. Schimbă starea în 'Q şi mişcă capul de citire la dreapta.
2. Schimbă starea în 'Q şi mişcă capul de citire la stânga.
3. Schimbă starea în 'Q şi nu mişcă poziţia capului de citire.
Decizia luată se bazează pe starea curentă şi simbolul de intrare, şi este
independent de stările/input-urile precedente. Valoarea funcţiei de
tranziţie pentru aceste maşini va fi perechea:
'( , ) ( , )Q x Q Rδ = sau '( , )Q L sau '( , )Q S
Dacă '( , ) ( , )Q x Q Rδ = , maşina trece în starea 'Q şi mişcă capul de citire cu
un simbol la dreapta; când '( , ) ( , )Q x Q Lδ = , maşina trece în starea 'Q şi
mişcă capul de citire cu un simbol la stânga; când '( , ) ( , )Q x Q Sδ = , capul
de citire nu se mişcă deloc şi simbolul de intrare x este recitit. Formal
avem:
Definiţia 2.8. O maşină cu stări finite deterministă bilaterală M se
compune din următoarele cinci obiecte:
1. O mulţime finită, nevidă 0 1Q { , , , }nQ Q Q= K . Elementele din Q se
numesc stări.
2. O mulţime finită, nevidă 1 2{ , , , }na a aΣ = K de simboluri admise
în şirul de intrare. Mulţimea Σ se numeşte alfabet pentru M.
3. O stare desemnată 0 QQ ∈ , numită stare iniţială.
4. O funcţie de tranziţie ( , )Q xδ definită pentru toate stările QQ∈
şi toţi x∈Σ . Pentru fiecare QQ∈ şi x∈Σ valoarea ( , )Q xδ este o
pereche '( , )Q Z , unde 'Q este altă stare din Q şi Z este unul din
simbolurile R, L sau S.
5. O mulţime nevidă F de stări din Q. Elementele lui F se numesc
stări finale sau acceptate.
O maşină cu stări finite de genul celei descrise mai sus va fi un cvintuplu
0{Q, , , , F}M Q δ= Σ şi se notează MSF2D.
Exemplu 2.11. Fie M o MSF2D cu patru stări 0Q (starea iniţială),
1Q , 2Q şi 3Q ; cu alfabetul de intrare { , , }a b cΣ = ; cu o stare finală 3Q ; şi cu
funcţia de tranziţie dată de tabelul din figura 2.26.
Input curent
a b C
0Q 0( , )Q R 1( , )Q R 2( , )Q R
1Q 0( , )Q R 3( , )Q L 1( , )Q L
2Q 0( , )Q R 1( , )Q R 2( , )Q S
S
t
ă
r
i 3Q 0( , )Q L 3( , )Q L 0( , )Q S
Figura 2.26. O maşină cu stări finite deterministă bilaterală.
Pentru a facilita descrierea mişcărilor unei MSF2D avem nevoie de o
metodă de descriere a configuraţie maşinii în orice moment dat. Deoarece
capul de citire se poate deplasa la stânga cât şi la dreapta, trebuie să
cunoaştem conţinutul şirului din dreapta capului de citire, ca şi din
stânga. Deci, o configuraţie a unei MSF2D va fi un triplet , ,Qσ τ , unde
σ este şirul de intrare din stânga capului de citire, Q este starea curentă şi
τ este şirul de intrare din dreapta capului de citire – presupunem că capul
de citire se află poziţionat pe primul simbol din τ . Întregul şir de intrare
este στ . σ şi τ pot fi şirul vid λ : Dacă σ λ= , şirul de intrare este pe
simbolul cel mai din stâng a şirului de intrare, iar τ λ= înseamnă că
întregul şir de intrare a fost citit. Figura 2.27. arată această configuraţie a
maşinii.
Figura 2.27. O MSF2D în configuraţia 0 1 1, ,k k pa a a Q a a+K K .
Mişcările posibile ale maşinii M sunt
1 1 2 2
0 1 1 1 1 1
1 1 1
, , dacă ( , ) ( , )
, , , , dacă ( , ) ( , )
, , dacă ( , ) ( , )
k k k p k
k k p k k p k
k k k k
a a a P a a Q a P R
a a a Q a a a a P a a Q a P L
a a P a a Q a P S
δ
δ
δ
+ + +
+ − +
+ +
=→ =
=
K K
K K K K
K K
Maşina porneşte, ca de obicei, în configuraţia 0 1 2, , kQ a a aλ K . Pot apărea
următoarele situaţii:
1. Maşina citeşte şirul de intrare σ în întregime şi ajunge în
configuraţia , ,Qσ λ , unde Q este o stare oarecare. În acest caz spunem
că M s-a oprit. De pildă, maşina M din exemplul 2.11. va trece prin
următoarea secvenţă de mişcări având ca input aabcacσ = :
← Şir de intrare
0 0 0, , , , , ,Q aabcac a Q abcac a Q bcacλ → → →
1 2 0 2, , , , , , , , se opreşteaab Q cac aabc Q ac aabca Q c aabcac Q λ→ → → → −
2. Maşina ajunge în configuraţia , ,Q aλ K şi ( , ) ( ', )Q a Q Lδ = ,
capul de citire citeşte cel mai din stânga simbol al şirul de intrare şi
instrucţiunile cer mutarea capului de citire la stânga. În acest caz vom
spune că maşina s-a blocat. De pildă, la input-ul abbbcaσ = , maşina din
exemplul 2.11. va avea următoarea secvenţă de mişcare:
0 0 1, , , , , ,Q abbca a Q bbca ab Q bcaλ → → →
3 3, , , , se suspendăa Q bbca Q abbcaλ→ → →
3. Maşina intră într-un ciclu infinit. De pildă, la input-ul
abccabσ = , mişcările maşinii M din exemplul 2.11. sunt:
0 0 1, , , , , ,Q abccab a Q bccab ab Q ccabλ → → →
2 1, , , , intră în cicluabc Q cab ab Q ccab→ → −
Definim limbajul acceptat sau generat de o MSF2D M ca fiind o mulţime
de şiruri σ pentru care maşina M, pornită în configuraţia 0, ,Qλ σ , se va
opri în configuraţia , ,Qσ λ , unde FQ∈ . Formal avem
**
0( ) { | , , , , , F}L M Q Q Qσ λ σ σ λ= ∈Σ → ∈
Ca urmare, dacă M este maşina din exemplul 2.11, ( )aabcac L M∈ , dar
abccab şi abbbca nu aparţin lui ( )L M . Maşinile cu stări finite obişnuite
pot fi văzute ca cazuri particulare ale maşinilor bidirecţionale:
( , ) ( ', )Q a Q Lδ ≠ sau ( ', )Q S în acest caz. Este de aşteptat ca clasa
limbajelor generate de MSF2D să fie mai mare decât clasa generată de
MSF obişnuite. Surprinzător, acesta nu este cazul. Avem următoarea
teoremă:
Teorema 2.7. Fie 0{Q, , , , F}M Q δ= Σ o MSF2D. Atunci există o
MSF deterministă K astfel încât ( ) ( )L M L K= .
Demonstraţie. Vom demonstra această teoremă sub ipoteza
suplimentară că maşina deplasează capul de citire ori la stânga ori la
dreapta, ( , ) ( ', )Q x Q Sδ ≠ . Aceasta o face pentru simplificarea expresiei;
demonstraţia pe cazul general se bazează pe aceeaşi idee.
Fie 0 1, , , nQ Q QK stările din M şi fie D un simbol nefolosit din M.
Pentru fiecare şir σ ∈Σ definim două funcţii ( )Qσφ şi ( , )Q xσψ în felul
următor. Dacă Q este o stare, definim ( )Qσφ ca fiind starea P, astfel încât
maşina M pornită în configuraţia , ,Qλ σ , se va opri în configuraţia
, ,Pσ λ . Aceasta înseamnă că M va citi toate simbolurile din σ şi se
opreşte în starea P. Dacă nu există un astfel de P, avem ( )Q Dσφ = . Ceea
ce va avea loc dacă, de exemplu, maşina M pornită cu input-ul σ , va
trece într-o buclă infinită, sau dacă se blochează. De pildă, în maşina
exemplului 2.11. avem 1 2( )cac Q Qφ = deoarece
1 2 0 2, , , , , , , , se opreşteQ cac c Q ac ca Q c cac Qλ λ→ → → −
Pe de altă parte, 1( )bca Q Dφ = fiindcă
1 3, , , , se blocheazăQ bca Q bcaλ λ→ −
Formal avem : Q Q { }Dσφ → ∪ dată prin
* dacă , , , ,( ) dacă nu există un astfel de
P Q PQD P
σλ σ σ λφ
→=
Funcţia σψ are două argumente – o starea Q şi un simbol x∈Σ şi se
defineşte astfel: Alegem ( , )Q xσψ ca fiind starea P astfel încât maşina M,
pornită în configuraţia , ,Q xσ va trece în configuraţia , ,P xσ în aşa
mod încât să nu existe R astfel încât
* *, , , , , ,Q x R x P xσ σ σ→ →
Cu alte cuvinte, ( , )Q xσψ este definită a fi prima stare P astfel încât,
dacă M este pornită în configuraţia , ,Q xσ , capul de citire a maşinii M
se mută la stânga şi rămâne în σ până când ajunge în configuraţia
, ,P xσ . Dacă nu există o astfel de stare, punem ( , )Q x Dσψ = .
Referindu-ne la exemplul 2.11. avem 3 0( , )bca Q a Qψ = deoarece
3 0 0, , , , , ,bca Q a bc Q aa bca Q a→ →
Formal, avem : Q Q { }Dσψ ×Σ→ ∪ dată prin
* *
dacă , , , , , dar nu există
( , ) astfel încât , , , , , , dacă nu există un astfel de
P Q x P x R P
Q x Q x R x P xD P
σ
σ σ
ψ σ σ σ
+ → ≠
= → →
În definiţia anterioară, notaţia , , , ,Q x P xσ σ+
→ înseamnă, că între
configuraţii, maşina execută un număr pozitiv de mişcări. Important de
reţinut despre funcţia ψ este: dacă ( , )Q x Pσψ = = , adică M porneşte în
configuraţia , ,Q xσ , capul de citire se deplasează la dreapta şi rămâne în
σ până când se ajunge în configuraţia , ,P xσ .
Observăm că există doar un număr finit de funcţii ψ şi φ , deoarece
mulţimile Q şi Σ sunt finite. Deci vor exista mai multe perechi 1σ şi 2σ în*Σ astfel încât
1 2( , ) ( , )Q x Q xσ σψ ψ= şi
1 2( ) ( )Q Qσ σφ φ= pentru orice QQ∈ şi
x∈Σ . Două astfel de şiruri se numesc echivalente şi notăm aceasta
1 2σ σ . Evident, relaţia este o relaţie de echivalenţă. Deoarece există
un număr finit de funcţii ψ şi φ , avem şi un număr finit de clase de
echivalenţă ale acestei relaţii.
Relaţia de echivalenţă are în plus următoarea proprietate:
Presupunem 1 2σ σ . Atunci pentru oricare τ ,
1 2( ) dacă şi numai dacă ( )L M L Mσ τ σ τ∈ ∈ (2.21)
Fie τ dat şi presupunem că 1 ( )L Mσ τ ∈ ; vream să demonstrăm că 2σ τ este
tot în ( )L M . Vom presupune τ λ≠ , în caz contrar concluzia este evidentă.
Fie 1xτ τ= şi considerăm mişcările maşinii M la input-ul 1 1xσ τ , în
particular, fie 1P starea din M când capul de citire ajunge prima dată la
simbolul x – primul simbol din τ : *
0 1 1 1 1 1, , , ,Q x P xλ σ τ σ τ→ şi în timpul
tranziţie între aceste configuraţii capul de citire rămâne în 1σ . Dar aceasta
înseamnă că 11 0( )P Qσφ= , şi fiindcă şirurile 1σ şi 2σ sunt echivalente, 1P
este de asemenea starea maşinii M când capul ei de citire ajunge prima
dată la x (pornind din configuraţia 0 2, ,Qλ σ τ ). Astfel, la input-urile 1 1xσ τ
şi 2 1xσ τ mişcările iniţiale ale maşinii M sunt
*
0 1 1 1 1 1*
0 2 1 2 1 1
, , , ,
, , , ,
Q x P x
Q x P x
λ σ τ σ τ
λ σ τ σ τ
→
→(2.22)
şi în cursul configuraţiilor intermediare, capul de citire rămâne în 1σ ,
respectiv 2σ . Fie 1 2, , , kP P PK stările maşinii M corespunzătoare
momentelor consecutive când capul de citire punctează pe x – primul
simbol din τ . (Urmărim în continuare mişcările din M la input-ul 1σ τ ).
Cu alte cuvinte, fie 1 2, , , kP P PK stări astfel încât
* * * *
1 1 1 1 2 1 1 1, , , , , ,kP x P x P xσ τ σ τ σ τ→ → → →L L (2.23)
unde mişcările din (2.23) sunt de felul următor
1. Înaintea ca configuraţia 1 1 1, ,P xσ τ să fie ajunsă, capul maşinii
M punctează în interiorul şirului 1σ .
2. Între configuraţiile 1 1, ,jP xσ τ şi 1 1 1, ,jP xσ τ+ capul de citire
punctează ori numai în 1σ ori numai în 1xτ .
3. După configuraţia 1 1, ,kP xσ τ capul de citire este numai în 1xτ .
Din definiţia funcţie ψ şi din faptul că 1 2σ σ rezultă, că mişcările
maşinii M la input-ul 2σ şi configuraţia 2 1 1, ,P xσ τ sunt
* * * *
2 1 2 2 2 2 2 2, , , , , ,kP x P x P xσ τ σ τ σ τ→ → → →L L (2.24)
Considerăm mişcările executate de M începând cu prima configuraţie din
(2.24). Dacă capul se deplasează la dreapta, mişcările vor fi identice cu
cele ale maşinii M pornite în prima configuraţie din (2.23). Aşadar, după
ce capul de citire se întoarce la x, M va fi în configuraţia 2 2 1, ,P xσ τ .
Dacă, pe de altă parte, capul de citire se deplasează la stânga atunci,
deoarece 12 1( , )P P xσψ= şi 2σ este echivalent cu 1σ , data următoare când
capul de citire întâlneşte x, M trece în starea 2P . Procedând la fel cu stările
2P şi 3P în loc de 1P , 2P etc., observăm că (2.24) este valabil. După ce M
ajunge în ultima configuraţie din (2.24), procedează ca şi când ar începe
cu ultima configuraţie din (2.23); cu alte cuvinte, acceptă 2σ τ . Dat fiind
faptul că rolul lui 1σ şi 2σ , din această discuţie, a fost simetric, ajungem
la concluzia că (2.21) este adevărat.
În final, putem construi maşina K. Alfabetul de intrare este identic
cu alfabetul din M. Stările corespund claselor de echivalenţă a relaţiei .
Dacă σ este un şir oarecare din *Σ , atunci σ denotă clasa de echivalenţă
care-l conţine pe σ . Simbolul de start va fi λ – clasă de echivalenţă care
conţine şirul vid. Ca stări acceptate pentru K sunt luate acele clase de
echivalenţă în a căror componenţă intră doar şiruri din ( )L M . (Se arată
uşor că dacă 1 2σ σ atunci, ori 1σ , 2σ sunt în ( )L M , ori amândoi nu sunt
în ( )L M ). Funcţia de tranziţie ∆ din K se defineşte în modul următor:
( , )x xσ σ∆ = (2.25)
Aceasta înseamnă că σ este o clasă de echivalenţă (o stare din K), şi x
este simbolul de intrare curent, atunci următoarea stare pentru K este
clasa de echivalenţă conţinând xσ . Evident, K este o maşină cu stări
finite deterministă, a cărei cap de citire se deplasează doar la dreapta.
Utilizând proprietatea (2.21), este uşor de arătat că ( ) ( )L M L K= . Q.E.D.
PROBLEME
Construiţi pentru fiecare din problemele 1 – 9 o maşină cu stări finite
deterministă care acceptă limbajul dat.
1. Mulţimea şirurilor de 0-uri şi 1-uri de lungime cel mult 5.
2. Mulţimea de şiruri din *{ , }a b având un număr par de b-uri.
3. Mulţimea de şiruri formate din a-uri şi b-uri având aa şi bb ca
subşiruri.
4. Limbajul tuturor constantelor întregi cu şi fără semn. Deci,
+345, -345 şi 345 aparţin toate limbajului.
5. Limbajul şirurilor peste *{0,1} care nu conţin subşirul 0011.
6. Limbajul *{ , }L a b⊆ şirurilor cu număr par de a-uri şi impar de
b-uri.
7. Mulţimea şirurilor de 0-uri şi 1-uri care încep cu 000 şi nu mai
conţin şirul 000. Deci, 000 este în limbaj, dar 0000 nu.
8. Limbajul şirurilor formate din 0 şi 1 în care subşirul 001 apare
cel puţin de trei ori.
9. Mulţimea de şiruri din *{ , }a b în care nici aa nici bb apar ca
subşir.
Construiţi pentru problemele 10 – 14 o maşină cu stări finite care acceptă
limbajul generat de gramatica indicată. Maşina nu trebuie să fie
deterministă.
10. | | |S aS bS b λ→
11. 0 |1S A B→ , 0 |1 | 0A C A→ , 1 |1 |1B B A→ , 0 | 0C A→
12. |S aA aB→ , |A aA bS→ , |B b bA→
13. | |S aS bB λ→ , |B aA b→ , |A aS aB→ â
14. | |S aS bS cA→ , A cB→ , B cC→ , | |C aC bC λ→
15. Construiţi o maşină cu stări finite deterministă care acceptă
fiecare din limbajele generate în problemele 10 – 14.
16. Pentru fiecare maşină din figura 2.28. construiţi o maşină
echivalentă deterministă.
Figura 2.28. Maşini cu stări finite nedeterministe.
17. Minimizaţi maşina cu stări finite a cărei funcţie de tranziţie este
dată în figura 2.16. (Întâi eliminaţi stările inaccesibile.)
18. Minimizaţi maşina cu stări finite din figura 2.29.
19. Completaţi demonstraţia teoremei 2.7. prin a arăta următoarele:
a. Dacă 1 2σ σ atunci sau 1σ şi 2σ sunt în ( )L M , sau
amândouă nu sunt în ( )L M .
b. Maşina K introdusă în demonstraţie este echivalentă cu
M.
Figura 2.29. Automate finite.