Vytvořil:
Jan Pejša, 9. května 2000
-
deterministický KA (nebo též zkráceně KA) definujeme následovně:
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.
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}.
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.
Dva konečné automaty M a N nazveme ekvivalentní, jestliže T(M) = T(N).
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ě.
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 (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ů.
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ů
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).
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).
Ř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:
Nechť L je jazyk rozpoznávaný nějakým NKA. Pak existuje DKA, který rozpoznává jazyk L.
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: