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, Σ, δ, q0, 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

q0 Î 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, Σ, δ, q0, F) akceptuje (rozpoznává, přijímá) slovo w, jestliže existuje koncový stav p Î F takový, že δ(q0, 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, Σ, δ, q0, F) akceptuje slovo w, jestliže existuje koncový stav p Î F takový, že [q0, 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 = ({q0, q1, q2, q3}, {0, 1}, δ, q0, {q0}).

 

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

 

                               

Šipka směrem k q0 znamená, že jde o počáteční stav a šipka směrem od q0 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, Σ, δ, q0, 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 Σ ® 2K

q0 Î 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 (q0, w) ^ (qf, e) a qf Î 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) = Up Î δ(q, x) δ(q, a)

 

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

 

Definice

Řekněme, že automat M akceptuje slovo w, pokud δ(q0, 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 = ({q0, q1}, {0, 1}, δ, q0, {q1}) má následující přechodovou funkci a diagram:

 

 

 

 

 

 

 

 


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