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.