Konečný automat

Konečný automat (anglicky finite state machine nebo finite automaton) je výpočetní model primitivního počítače, který se skládá z několika stavů a z několika přechodů a který dokáže přijmout nebo zamítnout předané slovo.

Příklad

Neformálně si konečný automat popíšeme pomocí stavového diagramu, který konečný automat popisuje:

Automat je tvořen stavy, na obrázku jsou to tři kulaté stavy q₀, q₁ a q₂. Mezi těmito stavy jsou přechody, to jsou ty šipky. V automatu dále musí být počáteční stav, to je stav q₀. Počáteční stav se často zobrazuje tak, že do něj směruje šipka, která nevychází z žádného stavu. Dále v automatu typicky bývá konečný stav, ten zobrazujeme dvojitou čárou, takže na obrázku je to stav q₂.

Takto sestavený automat přijímá nějaká slova. Do automatu tak vkládáme nějaká slova, automat tato slova zkusí přijmout. Pokud je přijme, odpoví automat ANO, pokud nepřijme, odpoví NE. Náš automat zkouší přijímat slova, která se skládají z písmen „a, b, c“, takže můžeme zkusit přijmout slovo „abbc“.

Začínáme v počátečním stavu q₀ a na vstupu je slovo „abbc“. Dále se budeme řídit šipkami.

Slovo procházíme klasicky zleva doprava, to znamená, že jako první budeme brát symbol „a“. Šipka pro vstup „a“ jde do stavu q₁, takže tam přejdeme a odstraníme symbol „a“ ze slova. Na vstupu máme slovo „bbc“:

Šipka pro vstup „b“ směruje zpátky do uzlu q₁. Opět odstraníme první písmeno a na vstupu máme slovo „bc“. Opět zůstaneme ve stavu q₁. Nakonec máme na vstupu slovo „c“. Ze stavu q₁ nás šipka pro vstup „c“ pošle do stavu q₂.

Už jsme vyčerpali všechna písmena ze vstupního slova a jsme ve stavu q₂, který je koncovým stavem. Tento konečný automat tak přijímá slovo „abbc“.

Pokud bychom na konci nebyli v přijímajícím stavu, automat by slovo nepřijal. Stejně tak by automat nepřijal slovo, pokud bychom v nějakém stavu neměli kam jít. Například pro vstup „ab“ bychom se dostali do stavu q₁ a tam bychom skončili — automat takové slovo nepřijímá. Pokud bychom otestovali slovo „aabbc“, tak máme opět smůlu, protože ze stavu q₁ nevede šipka pro písmeno „a“.

Konečný automat tak slouží k rozpoznání nějaké množiny slov. V praxi bychom automat mohli použít například k tomu, abychom zjistili, zda dané vstupní slovo je platný email.

Definice konečného automatu

Předchozí intuitivní představu o tom, co je to konečný automat musíme formalizovat, abychom s automaty mohli dále a lépe pracovat.

Řekneme, že konečný (deterministický) automat je pětice $\left<Q, \Sigma, \delta, q_0, F\right>$, kde

• Q je konečná množina stavů,
• $\Sigma$ (velká sigma) je abeceda (konečná množina symbolů/písmen),
• $\delta: Q \times \Sigma\longrightarrow Q$ je přechodová funkce,
• q₀ ∈ Q je počáteční stav,
• F ⊆ Q je množina koncových (přijímajících) stavů.

Vrátíme-li se k předchozímu automatu,

tak můžeme říci, že v množině stavů Q jsou tři stavy Q = {q₀, q₁, q₂}. Abeceda $\Sigma$ obsahuje písmena, ze kterých můžeme skládat slova, která pak bude automat přijímat nebo odmítat. Zde to pravděpodobně bude abeceda $\Sigma=\left\{a, b, c\right\}$, ale může to být i libovolná nadmnožina. Počáteční stav q₀ je stav q₀, na tom se nic nemění. Množina koncových stavů má v tomto automatu pouze jeden stav F = {q₂}.

Přechodovu funkcí pak rozumíme ty tři šipky s písmeny. Pokud vás mate značení $\delta: Q \times \Sigma\longrightarrow Q$, tak to jen znamená, že δ je funkce (možná lépe zobrazení), která bere dva parametry: stav z Q a písmeno z $\Sigma$. Po zavolání funkce vrátí nový stav. Naši přechodovou funkci bychom mohli tabulkou definovat takto:

$$ \begin{array}{cc|c} Q&\Sigma&\rightarrow Q\\\hline q_0&a&q_1\\ q_1&b&q_1\\ q_1&c&q_2\\ \end{array} $$

Pokud tak zavoláme δ(q₁, c), aplikujeme třetí řádek a funkce odpoví stavem q₂ — stejně jako diagram. Pokud jsme ve stavu q₁ a na vstupu je písmeno „c“, tak se dostaneme do stavu q₂. Než si formálně definujeme, co to znamená, že automat přijímá nějaké slovo, využijeme intuitivního chápání tohoto pojmu a ukážeme si nějaké další příklady.

Další příklady

1. Vytvořte automat, který pracuje nad binární abecedou, tj. $\Sigma=\left\{0,1\right\}$ a přijímá pouze slova, která končí jedničkou. Např. přijímá slova 1, 01, 000001, 0101011.

   

   Náš automat má dva stavy — počáteční q₀ a koncový q₁. Kdykoliv máme na vstupu číslici 1, tak přejdeme do koncového stavu q₁ a zůstaneme v něm. Naopak, pokud je na vstupu číslice 0, tak přejdeme do nekoncového stavu q₀ a také v něm zůstaneme.

2. Sestrojte automat nad binární abecedou, který přijímá pouze slova, jejichž počáteční písmeno je různé od koncového písmene.

   

   Automat se hned v prvním kroku dělí na dva „podautomaty“. Pokud slovo začíná nulou, vstoupí automat do levé části a už tam zůstane, pokud začíná jedničkou, přesune se do pravé části. Pak už je to klasika, pokud jsme v levé části a je na vstupu 1, přesuneme se do koncového stavu a už tam zůstaneme. Pokud je na vstupu 0, přesuneme se do stavu q₁, který koncový není.

   Na rozdíl od předchzích automatů má tento automat více koncových stavů, tj. F = {q₃, q₄}.

3. Sestrojte automat nad binární abecedou, který přijímá pouze slova, která neobsahují dvě nuly za sebou.

   

   Tento automat je zajímavý ze dvou důvodů: prvním je, že přijímá prázdné slovo. Do automatu můžeme zkusit vložit prázdné slovo a automat ho přijme, pokud je počáteční stav zároveň koncovým stavem, což se u tohoto automatu stalo. Protože prázdné slovo je slovo, které neobsahuje dvě nuly za sebou, tak to je to správné. Další zajímavostí je, že tento automat má všechny stavy koncové. Jediným případem, kdy by automat nepřijal slovo tak je, když by ze stavu nevedl žádný přechod. To se stane ve stavu q₁, který nemá přechod pro 0, protože pak by slovo obsahovalo dvě nuly za sebou.

4. Sestrojte automat nad abecedou {-,+,.,0,1,…,9}, který přijímá pouze slova, která reprezentují číslo. To znamená buď celé číslo jako např. 2, 548, 98263, nebo desetinné číslo jako např. 5584.48, 3.14 a obojí s verzí pro záporné číslo se znaménkem minus -2, -548, -3.14 a i s explicitně vyjádřeným pluskem, tj. +2, +548, +3.14. Zároveň musíme být schopni zapsat číslo 0.123 jen jako .123 (bez té nuly na začátku) a to včetně obou znamének. Zavedeme si pomocí značení, kdy místo toho, abychom vypisovali deset přechodů pro deset číslic budeme používat symbol N.

   

5. Sestrojte automat nad binární abecedou, který přijme pouze slova, která jsou tvaru 0ⁿ1ⁿ, což znamená, že slova mají na začátku určitý počet nul a následuje stejný počet jedniček. Příklady takových slov jsou 0011, 00001111, 01.

   Takový automat nelze sestavit, protože si nejsme nikde schopni „zapamatovat“ počet nul. Museli bychom vytvořit několik „podautomatů“, podobně jako ve druhém příkladě, jenže těch „podautomatů“ by muselo být nekonečně mnoho, pro každou hodnotu n jeden.

Formalizace výpočtu automatu

Už jsme si formálně definovali samotný konečný automat. Dále ještě musíme definovat, co takový automat vlastně dělá, tj. definujeme výpočet automatu.

Konfigurace automatu: Řekneme, že dvojice $\left<q, w\right> \in Q \times \Sigma^\ast$ je konfigurace automatu, kde q je aktuální stav, ve kterém se automat nachází a w je dosud nepřečtená část slova. $\Sigma^\ast$ značí uzávěr abecedy $\Sigma$, množinu všech slov, které lze poskládat z písmeny abecedy $\Sigma$. Součástí uzávěru je i prázdné slovo, které značíme $\varepsilon$.

Máme-li automat $\left<Q, \Sigma, \delta, q_0, F\right>$ a snažíme-li se přijmout slovo w, pak se automat nachází v počáteční konfiguraci <q₀, w>. Pokud se vrátíme k automatu

a budeme chtít přijmout slovo w = abbc, tak počáteční konfigurace bude <q₀, abbc>.

Krok výpočtu definujeme jako relaci $\mapsto$ mezi množinami $(Q\times\Sigma^\ast)\times(Q\times\Sigma^\ast)$, tj. mezi konfiguracemi automatu. Nechť w = w₀w₁… w_n představuje dosud nepřečtenou část slova w. Pak řekneme, že dvojice <q₁, w₀w₁… w_n> a <q₂, w₁… w_n> jsou v relaci $\mapsto$, zapíšeme jako

$$ \left<q_1, w_0w_1\dots w_n\right> \mapsto \left<q_2, w_1\dots w_n\right>, $$

právě tehdy, pokud δ(q₁, w₀) = q₂. Vrátíme-li se k našemu příkladu, tak počáteční konfigurace je <q₀, abbc>. Z diagramu vidíme, že pro vstup „a“ se můžeme posunout do stavu q₁. Můžeme tak napsat

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right>, $$

protože platí δ(q₀, a) = q₁. Tím jsme provedli jeden krok výpočtu — podívali jsme se, do jakého stavu bychom pro daný vstup (= první písmeno dosud nepřečtené části slova) měli jít, přešli jsme tam a odstranili jsme z nepřečtené části slova první písmeno. Tím jsme získali novou konfiguraci.

Reflexivní a transitivní uzávěr relace krok výpočtu značíme $\mapsto^\ast$. Pokud tak napíšeme $K_1 \mapsto^\ast K_2$, kde K₁, K₂ jsou konfigurace automatu, tak to znamená, že z konfigurace K₁ se přes několik kroků výpočtu dokážeme dostat do konfigurace K₂, neboli existuje konečná posloupnost konfigurací taková, že:

$$ K_1 \mapsto K_{11} \mapsto K_{12} \mapsto K_{13} \mapsto \dots \mapsto K_2 $$

Například v našem automatu platí $\left<q_0, abbc\right> \mapsto^\ast \left<q_1,bc\right>$, protože když provedeme dva kroky výpočtu, tak nám zbyde slovo „bc“ a zůstaneme ve stavu q₁. Tj. existuje tato posloupnost konfigurací:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> $$

Automat přijímá slovo w právě tehdy, pokud existuje q_f ∈ F takový, že $$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>$$ To znamená, že automat přijímá slovo w právě tehdy, pokud existuje nějaká posloupnost kroků výpočtu takových, že na konci této posloupnosti jsme přečetli celé slovo a nacházíme se v koncovém stavu automatu. Že jsme přečetli celé slovo je vyjádřeno tím, že je v konfiguraci na místě slova $\varepsilon$, což je prázdné slovo. Náš automat přijímá slovo abbc, protože existuje tato posloupnost konfigurací:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> \mapsto \left<q_1, c\right> \mapsto \left<q_2, \varepsilon\right> $$

a stav q₂ je koncový stav, q₂ ∈ F.

Jazyk přijímaný automatem je množina všech slov, které automat přijímá. Jazyk automatu A budeme značit jako L(A). Platí tak, že $L(A) \subseteq \Sigma^\ast$ a

$$ L(A) = \left\{w \in \Sigma^\ast,|,A \mbox{ přijímá slovo } w\right\} $$

Regulární jazyk je takový jazyk, který je přijímán nějakým konečným automatem.

Dva konečné automaty jsou ekvivalentní pokud přijímají stejný jazyk. Tj. automaty A₁ a A₂ jsou ekvivalentní, pokud platí L(A₁) = L(A₂).

Zdroje

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools