Konečné automaty

Obsah:

Deterministické konečné automaty

Příklad

Nedeterministické konečné automaty

Příklad

Zpět na úvodní stránku

Vytvořil: Jan Pejša, 9. května 2000

Deterministické konečné automaty

- deterministický KA (nebo též zkráceně KA) definujeme následovně:

Definice

Konečný automat M nad abecedou Σ je pětice (K, Σ, δ, q₀, F), kde jednotlivé komponenty mají tento význam:

K – konečná neprázdná množina stavů

Σ – konečná neprázdná množina symbolů; abeceda

δ – přechodová funkce; δ: K x Σ ® K

q₀ Î K – počáteční stav

F Í K – množina koncových stavů

Sémantiku konečných automatů lze definovat dvěma způsoby. První z nich používá tzv. zobecněnou přechodovou funkci a druhý tzv. konfigurace automatu.

Definice

Z přechodové funkce δ lze induktivně zkonstruovat zobecněnou přechodovou funkci δ´: K x Σ´ ® K.

δ(q, a) = δ(q, a) a Î Σ

δ´(q, xa) = δ(δ´(q, x), a) a Î Σ x Î Σ⁺

Místo δ´ lze také psát pouze δ. Na symbolech se totiž funkce δ i δ´ rovnají a u slov delších než 1 symbol půjde automaticky o zobecnění δ.

Definice – Sémantika KA I.

Řekněme, že konečný automat M = (K, Σ, δ, q₀, F) akceptuje (rozpoznává, přijímá) slovo w, jestliže existuje koncový stav p Î F takový, že δ(q₀, w) = p.

Dále T(M) bude značení pro jazyk akceptovaný automatem M, tedy T(M) = {w Î Σ^*: M akceptuje w}.

Definice

Konfigurací automatu M nazveme libovolnou dvojici [q, x], kde q Î K je stav a x Î Σ^* je slovo.

Relaci ^ na množině konfigurací automatu M (krok výpočtu) definujeme takto: [q, ax] ^ [q, x],
pokud δ(q, a) = p.

Definice – Sémantika KA II.

Řekněme, že konečný automat M = (K, Σ, δ, q₀, F) akceptuje slovo w, jestliže existuje koncový stav p Î F takový, že [q₀, w] ^^* [p, e].

Jazyk akceptovaný automatem M již definujeme stejně jako v definici 3.

Definice

Dva konečné automaty M a N nazveme ekvivalentní, jestliže T(M) = T(N).

Poznámka

Funkce δ může být (a také často bývá) parciální.

Konečné automaty lze reprezentovat několika různými způsoby:

a) pětice uvedená v definici 1

b) tabulka přechodové funkce δ se specifikací počátečního a koncových stavů

c) stavový diagram

d) výpočetní strom

Tyto reprezentace bude nejlépe ukázat na příkladě.

Příklad

Nechť je dán konečný automat M = ({q₀, q₁, q₂, q₃}, {0, 1}, δ, q₀, {q₀}).

Přechodovou funkci δ specifikuje následující tabulka:

Šipka směrem k q₀ znamená, že jde o počáteční stav a šipka směrem od q₀ znamená, že je to zároveň jediný koncový stav. Následuje ukázka stavového diagramu a výpočetního stromu pro tento automat.

Ve výpočetním stromu se snažíme zachytit všechny možné posloupnosti stavů. Každá větev dává právě jedno odvození a pokud končí, sestavíme odečtením symbolů na této větvi slovo přijímané automatem. Výpočetní strom bývá často nekonečný. V jeho kořeni je počáteční stav, v listech mohou být pouze koncové stavy.

Stavový diagram dostaneme z výpočetního stromu tak, že všechny výskyty téhož stavu sjednotíme do jediného uzlu. Dostáváme tak graf, ve kterém na počáteční stav ukazuje šipka zvenku a koncové stavy jsou označeny dvojitým kroužkem.

Nedeterministické konečné automaty

Nedeterministické konečné automaty (NKA; deterministický KA bude dále DKA) poskytují volbu při přechodu stavů. Oborem hodnot přechodové funkce nebudou nyní pouhé stavy automatu, ale všechny podmnožiny množiny stavů.

Definice

Nedeterministický konečný automat M nad abecedou Σ je pětice (K, Σ, δ, q₀, F), kde jednotlivé komponenty mají tento význam:

K – konečná neprázdná množina stavů

Σ – konečná neprázdná množina symbolů; abeceda

δ – přechodová funkce; δ: K x Σ ® 2^K

q₀ Î K – počáteční stav

F Í K – množina koncových stavů

Definice

Konfigurací automatu M nazveme libovolnou dvojici [q, x], kde q Î K je stav a x Î Σ^* je slovo
(žádná změna).

Relaci ^ na množině konfigurací automatu M (krok výpočtu) definujeme takto: [q, ax] ^ [q, x],
pokud p Î δ(q, a).

Automat akceptuje slovo w Î Σ^*, pokud (q₀, w) ^ (q_f, e) a q_f Î F (žádná změna).

Poznámka

Přechodovou funkci δ můžeme opět rozšířit na definiční obor K x Σ^* takto:

δ(q, e) = {q}

δ(q, xa) = U_{p Î δ(q, x)} δ(q, a)

U nedeterministických KA provádíme navíc rozšíření na definiční obor 2^K x Σ^*: δ(P, x) = U_{p Î P} δ(p, x).

Definice

Řekněme, že automat M akceptuje slovo w, pokud δ(q₀, w) Ç F ¹ Æ.

- vztah mezi deterministickými a nedeterministickými KA udává následující věta:

Věta

Nechť L je jazyk rozpoznávaný nějakým NKA. Pak existuje DKA, který rozpoznává jazyk L.

Příklad

Nedeterministický konečný automat M = ({q₀, q₁}, {0, 1}, δ, q₀, {q₁}) má následující přechodovou funkci a diagram:

Vytvoříme k němu deterministický automat M´ = (K´, {0, 1}, δ´, {q₀}, F),
kde množina stavů je K´ = {Æ, {q₀}, {q₁}, {q₀, q₁}} a konečné stavy jsou F´ = {{q₁}, {q₀, q₁}}. Přechodová funkce δ´ je pak dána následující tabulkou a diagramem: