PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Konečný automat

Zobrazit kapitoly článku
  1. Konečný automat
  2. Totální automat
  3. Nedeterministický konečný automat
  4. Simulace NKA
  5. Převod NKA na DKA

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:

Příklad jednoduchého konečného automatuPříklad jednoduchého konečného automatu

Automat je tvořen stavy, na obrázku jsou to tři kulaté stavy q0, q1 a q2. 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 q0. 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 q2.

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 q0 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 q1, 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 q1. Opět odstraníme první písmeno a na vstupu máme slovo „bc“. Opět zůstaneme ve stavu q1. Nakonec máme na vstupu slovo „c“. Ze stavu q1 nás šipka pro vstup „c“ pošle do stavu q2.

Už jsme vyčerpali všechna písmena ze vstupního slova a jsme ve stavu q2, 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 q1 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 q1 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_0 \in Q\) je počáteční stav,
  • \(F \subseteq 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 = {q0, q1, q2}. 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 q0 je stav q0, na tom se nic nemění. Množina koncových stavů má v tomto automatu pouze jeden stav F = {q2}.

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 δ(q1, c), aplikujeme třetí řádek a funkce odpoví stavem q2 – stejně jako diagram. Pokud jsme ve stavu q1 a na vstupu je písmeno „c“, tak se dostaneme do stavu q2. 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í q0 a koncový q1. Kdykoliv máme na vstupu číslici 1, tak přejdeme do koncového stavu q1 a zůstaneme v něm. Naopak, pokud je na vstupu číslice 0, tak přejdeme do nekoncového stavu q0 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 q1, který koncový není.

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

  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 q1, 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 0n1n, 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 \(\left< q_0, w\right>\). Pokud se vrátíme k automatu

a budeme chtít přijmout slovo w = abbc, tak počáteční konfigurace bude \(\left< q_0, abbc\right>\).

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 = w0w1wn představuje dosud nepřečtenou část slova w. Pak řekneme, že dvojice \(\left< q_1, w_0w_1\dots w_n\right>\) a \(\left< q_2, w_1\dots w_n\right>\) 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 δ(q1, w0) = q2. Vrátíme-li se k našemu příkladu, tak počáteční konfigurace je \(\left< q_0, abbc\right>\). Z diagramu vidíme, že pro vstup „a“ se můžeme posunout do stavu q1. Můžeme tak napsat

\[\left< q_0, abbc\right> \mapsto \left< q_1, bbc\right>,\]

protože platí δ(q0, a) = q1. 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 K1, K2 jsou konfigurace automatu, tak to znamená, že z konfigurace K1 se přes několik kroků výpočtu dokážeme dostat do konfigurace K2, 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 q1. 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 \in 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 q2 je koncový stav, \(q_2 \in 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 A1 a A2 jsou ekvivalentní, pokud platí L(A1) = L(A2).

Zdroje #

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace