Konstrukce rozpoznávacích konečných automatů

Vytvořte přechodové grafy konečných automatů, které rozpoznávají řetězce jistých vlastností nad abecedou {a, b}.

Řetězec obsahuje sudý počet znaků "a".

Při řešení máme dvě možnosti: považovat 0 za sudé číslo:

nebo uvažovat pouze přirozená čísla, mezi něž nula nepatří; nejméně tedy akceptujeme dva znaky "a":

Konstrukce automatů je snadná: na "sudosti" počtu znaků "a" se může podílet pouze znak "a" na vstupu. Proto bude automat přecházet mezi stavy jen znakem "a". Stavy pak vyjadřují, zda automat načetl sudý, lichý, případně nulový počet znaků "a". Znak "b" nemá na sledovanou vlastnost řetězce vliv, proto automat na jeho přítomnost ve vstupu nereaguje, resp. zůstává ve stejném stavu.

Řetězec obsahuje právě dva znaky "a"

Při konstrukci napřed sestavíme stavy, které postupně znamenají "žádný znak a nebyl nalezen", "byl nalezen jeden znak a", "byly nalezeny dva znaky a". Poslední z nich je stavem akceptačním. Pak připojíme další stav, do něhož se automat dostane načtením třetího znaku a; z něj už se pak nedostane (absorpční stav).

Řetězec obsahuje nejméně dva znaky "a"

Při konstrukci opět využijeme absorpční stav, který bude současně stavem akceptačním:

Řetězec začíná sekvencí "abb-"

Napřed sestrojíme sekvenci stavů, která akceptuje řetězec "abb". Poté připojíme dva absorpční stavy: jeden akceptační, do něhož se automat dostane po načtení "abb", druhý chybový, do něhož se automat dostane v ostatních případech.

Řetězec obsahuje sekvenci "abba"

Nyní je situace poněkud obtížnější, ale jednoduchým postupem se dá automat rovnž snadno sestavit. Nejprve vytvoříme standardní sekvenci stavů, která odpovídá situacím "načtený vstup končí na a", "končí na ab", končí na "abb", končí na "abba". V posledním stavu zřejmě řetězec obsahuje sekvenci "abba", a proto z něj můžeme udělat absorpční akceptační stav. V ostatních stavech musíme uvažovat způsobem, který si ukážeme na stavu "-ab".

Je-li automat ve stavu "-ab" a na vstupu se objevví "b", končí vstup sekvencí "abb". Jelikož máme pro tuto situaci připravený stav "-abb", může do něj automat přejít. Pokud se ale na vstupu objeví "a", končí vstup sekvencí "aba", což je pro nás mírně nezajímavá situace. Pozornější analýzou zjistíme, že koncová sekvence "aba" znamená, že na konci řetězce se rovněž vyskytují sekvence "ba", respektive "a". Právě poslední jmenovaná ale odpovídá stavu, který vede k rozpoznání řetězce, a proto do něj automat může přejít; říkáme, že řetězec "a" je perspektivním prefixem řetězce "abba".

Tak můžeme sestavit následující tabulku, kde podtržení znamená jednak "část začátku sekvence abba", jednak stav, do něhož automat přechází:

Nyní bez potíží nakreslíme přechodový graf:

Řetězec nezačínající "bba", obsahující "babb" a nekončící na "aa"

Tento příklad záměrně ukazuje složenou, poměrně komplikovanou podmínku, kterou na řetězec klademe. Ke konstrukci automatu můžeme přistoupit buď systematicky, nebo obdobně jako v minulých případech - postupným rozvíjením jednoduchého automatu. Systematický přístup ukážeme zachvíli; zkusme nejprve automat sestavit "ručně".

Při ručním postupu můžeme uvažovat následovně. Začneme sekvencí stavů, která bude zjišťovat, zda automat začíná sekvencí "bba". Pokud začíná, pak je zřejmé, že řetězec nesmí být akceptován, protože nás zajímají řetězce, které nezačínají sekvencí "bba". Na konci této sekvence proto umístíme absorpční "chybový" stav. Pokud řetězec ze sekvence "bba" uteče, víme, že řetězec na "bba" nezačíná a můžeme se starat o další podmínky.

Dále sestavíme stavy a přechody, které odpovídají rozpoznání podřetězce "babb", a to stejným způsobem, jako v předchozím příkladu. Na rozdíl od něj ale do stavů "-", "-b", "-ba", "-bab", "-babb" můžeme přejít z některého ze stavů, které analyzují začátek řetězce.

Pokud má řetězec splňovat všechny tři podmínky, musí se zjevně napřed rozhodnout, že obsahuje podřetězec "babb", a až naposled rozhodnout, zda končí znaky "aa". Proto můžeme detekci podoby konce řetězce připojit až za stav "babb-".

Tak získáme konečnou podobu automatu. Horní řada stavů odpovídá detekci "bba" na začátku, prostřední řada detekci podřetězce "babb", spodní řada detekci "aa" na konci vstupu. Nezapomeneme označit akceptační stavy v souladu s podmínkou, že řetězec nesmí končit na "aa".

Řetězec obsahující "ba" a neobsahující "bbb"

K sestavení automatu můžeme přistoupit systematicky. Na rozdíl od "ručního" přístupu použitého v předchozím příkladu vede obvykle systematický přístup k větším automatům, výhodou ale je mechanický postup, který může snadno zastat počítač. Tím se dostáváme k podstatné výhodné vlastnosti konečných automatů: velmi často je lze konstruovat, optimalizovat či spojovat prostřednictvím počítačového programu, který se nesplete a který dokáže zvládnout automaty o stovkách tisíc stavů.

Jako ukázku takového algoritmu si ukážeme propojení dvou jednoduchých automatů do jednoho.

Se zkušenostmi, které máme, můžeme snadno sestavit automat, který zjistí, zda řetězec obsahuje sekvenci "ba"; všem takovým řetězcům budeme říkat jazyk L1.

Automat detekující slova obsahující sekvenci "ba"

Formálně zapíšeme definici automatu A₁:

• množina stavů Q₁ = {1, 2, 3},
• vstupní abeceda Σ = {a, b},
• přechodová funkce δ₁ podle grafu výše,
• startovací stav q₁₀ = 1,
• množina koncových stavů F₁ = {3}.

Obdobně sestavíme automat A₂ akceptující slova jazyka L₂, tj. slova neobsahující "bbb":

Automat detekující slova neobsahující sekvenci "bbb"

Formálně zapíšeme definici automatu A₂:

• množina stavů Q₂ = {A, B, C, D},
• vstupní abeceda Σ = {a, b},
• přechodová funkce δ₂ podle grafu výše,
• startovací stav q₂₀ = A,
• množina koncových stavů F₂ = {A, B, C}.

Nyní vytvoříme automat A akceptující slova jazyka L = L₁ ∩ L₂, tj. průnik jazyků L₁ a L₂. Takový automat pomyslně obsahuje oba základní automaty A₁ a A₂. Jelikož každý z nich se může teoreticky nacházet v libovolném svém stavu, určíme množinu stavů automatu A jako kartézský součin Q₁ × Q₂:

• množina stavů Q = Q₁ × Q₂ = {A1, A2, A3, B1, B2, B3, ..., D3}.

Na počátku rozpoznávání by měly být oba základní automaty v počátečním stavu, čili

• startovací stav q₀ = A1.

Přechodovou funkci určíme mechanicky: je-li například automat A ve stavu A1 a na vstupu je "b", měl by automat A₁ přejít do stavu 2 a automat A₂ do stavu B; proto přejde automat A do stavu B2. Stejně sestavíme přechodovou funkci pro ostatní stavy:

Automat detekující slova obsahující "ba" a neobsahující "bbb".
Stavy označené šedě jsou teoreticky možné, ale prakticky nedosažitelné

Budeme-li stavy automatu A psát ve formě uspořádané dvojice <q₁, q₂>, kde q₁ ∈ Q₁, q₂ ∈ Q₂, potom můžeme formálně přechodovou funkci δ zapsat prostřednictvím funkcí δ₁ a δ₂: automat A reaguje na vstup x ∈ Σ podle funkce δ

• δ(<q_i, q_j>, x) =  < δ₁(q_i, x), δ₂(q_j, x) >.

Stejně tak můžeme formálně zapsat množinu koncových stavů F: pokud chceme, aby automat A akceptoval průnik jazyků L₁, L₂, potom se musí automat A₁ nacházet v některém ze stavů F₁ a současně se musí automat A₂ nacházet v některém ze stavů F₂, tj.

• F =  { <q_i, q_j> | q_i ∈ F₁  ∧  q_j ∈ F₂ }

Sjednocení jazyků

Stejným systematickým postupem můžeme vytvořit automat A, který akceptuje slova jazyka L = L₁ ∪L₂, kde jazyky L₁ a L₂ jsou rozpoznávány automaty A₁ a A₂. Neformálně řečeno můžeme vytovřit automat rozpoznávající slova, která by rozpoznal automat A₁ nebo automat A₂.

Jediným rozdílem oproti předchozímu postupu bude odlišná formulace koncových stavů - místo logického "a" použijeme logické "nebo":

• F =  { <q_i, q_j> | q_i ∈ F₁  ∨  q_j ∈ F₂ }

Coby příklad můžeme sestavit automat akceptující sjednocení jazyků L₁ a L₂, kde

• L₁ = { w | w ∈ {a, b}^*,  w obsahuje podřetězec "abb" a současně nekončí "aa"},
• L₂ = { w | w ∈ {a, b}^*,  počet znaků "b" je dělitelný 3}

(Pozn.: zápis w ∈ {a, b}^* označuje všechny řetězce, které lze sestavit ze znaků "a", "b")

Nejprve sestavíme automaty A₁ a A₂:

Automat A₁

Automat A₂

Rutinně sestavíme složený automat:

Hotový automat A. Modře zvýrazněné stavy jsou stavy koncovými; výstupní šipky už by obrázek příliš zamotaly

Musíme uznat, že hotový automat není příliš přehledný a jeho přechodový graf se konstruuje poměrně nepohodlně. Zápis přechodové funkce tabulkou je ale triviální. V prvním kroku doplníme, jak by na vstup reagoval automat A₁. Všimněme si, že řádky jsou v tabulce řazeny tak, aby byla "písmena" (čili stavy automatu A₁) pohromadě. Díky tomu bude v každé "sekci" reakce automatu stejná.

Řádky tabulky si přetřídíme, abychom viděli pohromadě stavy automatu A₂, a doplníme jeho reakci:

Nakonec označíme vstupní a výstupní stavy: podle automatu A₁ to mají být všechny stavy "D?", "E?", podle automatu A₂ to mají být všechny stavy "?1". V případě sjednocení jazyků označíme jako výstupní ty stavy, kde platí alespoň jedna podmínka.

A je to. Poučení je nasnadě: při reprezentaci přechodové funkce (grafem, tabulkou, stromem) využíváme vždy takovou reprezentaci, která je v daný okamžik nejvýhodnější.