Konečný automat

Co je to konečný automat ?

Konečný automat je teoretický výpočetní model používaný v informatice pro studium formálních jazyků. Popisuje velice jednoduchý počítač, který může být v jednom z několika stavů, mezi kterými přechází na základě symbolů, které čte ze vstupu. Množina stavů je konečná (odtud název), konečný automat nemá žádnou další paměť, kromě informace o aktuálním stavu. Konečný automat je velice jednoduchý výpočetní model, dokáže rozpoznávat pouze regulární jazyky. Konečné automaty se používají při vyhodnocování regulárních výrazů, např. jako součást lexikálního analyzátoru v překladačích.

Konečný automat můžeme definovat jako uspořádanou pětici (Q, ∑, δ, q0, F) kde:

  • Q : Konečná neprázdná množina stavů
  • ∑ : Konečná množina vstupních symbolů, take nazývaná abeceda. Neplést si se vstupním řetězcem.
  • q0 : počáteční stav
  • F : Množina koncových stavů (je podmnožinou Q)
  • δ : Přechodová funkce mezi stavy

Popis činnosti konečného automatu

Na počátku se automat nachází v definovaném počátečním stavu. Dále v každém kroku přečte jeden symbol ze vstupního řetězce a přejde do stavu, který je dán hodnotou, která v přechodové tabulce odpovídá aktuálnímu stavu a přečtenému symbolu. Poté pokračuje čtením dalšího symbolu ze vstupního řetězce, dalším přechodem podle přechodové tabulky atd.

Podle toho, zda automat skončí po přečtení vstupního řetězce ve stavu, který patří do množiny přijímajících stavů, platí, že automat buď daný vstupního řetězec přijal, nebo nepřijal. Množina všech řetězců, které daný automat přijme, tvoří regulární jazyk.

Pozn. Pokud má automat na vstupu symbol, ke kterému neexistuje přechodová funkce ze současného stavu, tak automat vstupní řetězec nepřijal. (Automat obsahuje tzv. dead state, do kterého kterého se automat přechodovou funkcí dostane, ale již se z něj nikdy nedostane) Toto nemusí platit u NFA, kde je možnost být ve více stavech najednou.

Reprezentace konečného automatu

Konečný automat lze reprezentovat několika způsoby. Bude následovat příklad vyjádření totožného konečného automatu třemi různými způsoby.

Reprezentace výčtem prvků

A = (Q, ∑, δ, q0, F) - naše uspořádaná pětice
Q = (q0,q1,q2) - množina stavů, které automat obsahuje
∑ = (0,1) - symboly rozpoznávané konečným automatem
F = (q1)

δ(q0,0) = q1 (Toto je přechodová funkce která říká "Když jsi ve stavu q0 a na vstupu je symbol '0', tak jdi do stavu q1" )
δ(q0,1) = q2
δ(q1,0) = q1
δ(q1,1) = q0
δ(q2,0) = q2
δ(q2,1) = q2

Reprezentace tabulkou

A = (Q, ∑, δ, q0, F) - naše uspořádaná pětice
Q = (q0,q1,q2) - množina stavů, které automat obsahuje
∑ = (0,1) - symboly rozpoznávané konečným automatem
F = (q1)

Současný stav01
->q0q1q2
q1q1q0
q2q2q2

(Všimněme si, že reprezentace se týká čistě přechodových funkcí)

Reprezentace grafem

A = (Q, ∑, δ, q0, F) - naše uspořádaná pětice
Q = (q0,q1,q2) - množina stavů, které automat obsahuje
∑ = (0,1) - symboly rozpoznávané konečným automatem
F = (q1)

Příklad konečného automatu
obr. 1: Jednoduchý příklad (deterministického) konečného automatu

Deterministický konečný automat (DFA) vs Nedeterministický konečný automat (NFA)

Konečné automaty můžeme dělit na dva druhy.

Deterministický

  • Nepřijímá prázdný řetězec
  • Pro každý vstupní znak existuje nejvýše jeden stav, do kterého může automat přejít. Může se tedy v jednu chvíli nacházet právě v jednom stavu.
  • Z každého stavu by měli existovat přechodové funkce pro každý symbol z množiny ∑.
  • Přechodová funkce má tvar δ = Q x ∑ -> Q

Nedeterministický

  • Přijímá prázdný vstupní řetězec
  • Z jednoho stavu se lze dostat do více stavů zároveň. Automat se tedy může nechávat ve více stavech zároveň a pokud je po zpracování vstupního řetězce alespoň jeden z těchto stavů stavem konečným, je řetězec přijat.
  • Jednotlivé stavy nemusí mít přechodové funkce pro všechny symboly z množiny ∑.
  • Přechodová funkce má tvar δ = Q x ∑ -> 2Q

Výše uvedené příklady reprezentace byly určeny pro DFA. Nyní vytvoříme podobné příklady pro NFA.

A = (Q, ∑, δ, q0, F) - naše uspořádaná pětice
Q = (q0,q1) - množina stavů, které automat obsahuje
∑ = (ε,0,1) - přidali jsme symbol 'ε', značící přechod bez nutnosti zpracování vstupního symbolu
F = (q1)

Současný stav01
->q0q1nill
q1q0q0,q1

Grafická reprezentace by vypadala takto:

Nedeterministický konečný automat
obr. 2: Nedeterministický konečný automat

Všimněme si "nedeterminističnosti" v podobě možnosti dostat se pomocí jedné přechodové funkce do dvou stavů zároveň.

Konverze NFA na jeho DFA ekvivalent

Platí, že každý DFA je ve skutečnosti NFA, ale ne naopak. DFA je podmnožinou NFA. Zároveň platí, že ke každému NFA lze sestrojit jeho DFA ekvivalent.

Proč ? Vychází to z definic přechodových funkcí
Pro DFA : δ = Q x ∑ -> Q
Pro NFA : δ = Q x ∑ -> 2Q

Definice přechodové funkce pro NFA v sobě obsahuje definici přechodové funkce pro DFA. Ale ne naopak. NFA sice může přejít do více stavů zároveň za pomocí jednoho symbolu a může přejít do stavu bez zpracování symbolu, ale také nemusí. Na základě toho můžeme říct, že každý DFA je NFA, akorát tento NFA nemá žádné příznaky NFA.

Nyní pojďme převést náš NFA výše na DFA.

DFA nesmí mít více přechodů z jednoho stavu pro ten a samý symbol a měli by existovat přechodové funkce pro všechny symboly abecedy pro každý stav. Pokud by se v NFA nacházeli přechody Epsilon, tak se tyto dva stavy sloučí v jeden.

Postup je následovný (Nejlépe se dělá podle přechodové tabulky):

  • Přidáme tzv. dead state. Do tohoto stavu budeme svádět neexistující přechody již existujících stavů.
  • Pokud máme Epsilon přechody, zbavíme se jich tak, že přechod nahradíme přechody, které vedou ze stavu do kterého by jsme se skrze Epsilon přechod dostaly. Příklad zbavení se Epsilon přechodů můžeme najít v kapitole Konečné automaty a regulární jazyky.
  • Přidáme nový stav, pokud máme více přechodových funkcí z jednoho stavu pro ten a samý symbol, tedy přecházíme do dvou stavů zároveň. Tyto stavy spojíme do jednoho nového.
  • Aplikujeme operaci union na přechodové funkce stavů, které tento nový stav "pohltil", čímž získáme přechodové funkce pro náš nový stav.
  • Pokud jsou přechodové funkce nového stavu totožné s přechodovými funkcemi jednoho ze stavů, který byl použít k vytvoření nového, tak starý stav smažeme.

Úspěšně jsme naši DFA ekvivalent k našemu NFA z obrázku č. 2.

A = (Q, ∑, δ, q0, F) - naše uspořádaná pětice
Q = (q0,q1,q2) - množina stavů, které automat obsahuje
∑ = (0,1) - jedná se o DFA, nemá tedy možnost zpracovat prázdný řetězec F = (q1)

Současný stav01
->q0q1q2
q01q0q01
q2q2q2
Deterministická verze konečného automatu z obrázku č. 2
obr. 3: Deterministická verze konečného automatu z obrázku č. 2

Konečné automaty a regulární jazyky

Regulární jazyk je jediným druhem jazyka, který může být akceptován konečným automatem. Regulární jazyk je vyjádřen regulárním výrazem a tento regulární výraz může být vyjádřen v podobě konečného automatu a naopak, konečný automat může být vyjádřen regulárním výrazem. Pro každý regulární výraz R existuje konečný automat, který přijímá řetězce generované tímto regulárním výrazem.

Pro sestavení FA z regulárního výrazu postupujeme následovně:

  • Převedeme výraz na NFA s Epsilon přechody
  • Odstraníme Epsilon přechody
  • Převedeme NFA na DFA

Pro převod výrazu na NFA využijeme následující 'stavební bloky'

Základní konečné automaty pro regulární výrazy
obr. 4: Základní konečné automaty pro regulární výrazy.
Převzato z: https://www.tutorialspoint.com/how-to-convert-regular-expression-to-finite-automata

Řekněme, že máme regulární výraz, který generuje sekvenci písmen 'a' a 'b' nebo jedno jediné 'a'.
a + (a+b)*

Budeme tedy postupovat zleva doprava a krok po kroku vytvoříme náš NFA.

Inicializační krok
obr. 5: Inicializační krok
Rozdělení výrazu pomocí + operátoru
obr. 6: Rozdělení výrazu pomocí + operátoru
Přidání Epsilon přechodu, aby jsme mohli být v obou stavech najednou
obr. 7: Přidání Epsilon přechodu, aby jsme mohli být v obou
stavech najednou

Všimněme si, že krom epsilon operátoru jsme vycházeli čistě ze stavebních bloků popsaných na obrázku číslo 4 tak, že s každým rozdělením jsme přidali nový stav do kterého vede odpovídající přechodová funkce.

Nyní eliminujeme Epsilon přechod tak, že zduplikujeme přechody, které vedou ze stavu do kterého se skrze Epsilon dostaneme. Těmito přechody do patřičných stavů Epsilon nahradíme.

Nahrazení Epsilon přechodu
obr. 8: Nahrazení Epsilon přechodu

Nyní máme NFA, který odpovídá našemu regulárnímu výrazu. Na základě postupu z kapitoly Konverze NFA na jeho DFA ekvivalent nakonec vytvoříme ekvivalentní DFA.

DFA verze NFA
obr. 9: DFA verze NFA

Pozn. Kdyby to bylo nutné, bylo by potřeba doplnit dead state tak, aby všechny stavy měly přechodové funkce ke všem prvkům vstupní abecedy.

Citace