Automaty a formální jazyky
Přednáška III.
Ekvivalence a minimalizace automatů
Konečné automaty - nedeterministické
Hledání dosažitelných stavů -
algoritmus
• Princip: K již známým dosažitelným stavům
přidáváme postupně v jednotlivých krocích ty
stavy, do nichž se lze dostat jedním
symbolem z již známých dosažitelných stavů.
• Počátek: počáteční stav je vždy dosažitelný.
• Konec: v daném kroku už nepřibude žádný
další stav.
Redukovaný automat
• Definice: Konečný automat je redukovaný,
když jsou všechny jeho stavy dosažitelné a
nejsou si ekvivalentní.
• Definice: Automat A je reduktem automatu
B, jestliže jsou si automaty ekvivalentní a A je
redukovaný automat.
• Věta: Ke každému konečnému automatu
existuje jeho redukt.
S pomocí redukce rozhodujeme
• Definuje automat vůbec nějaký jazyk? Jen tehdy, máli
dosažitelný alespoň jeden koncový stav.
• Definuje automat celý uzávěr nad abecedou? Pokud
ano, potom jej lze redukovat na jeden jediný stav.
• Jsou dva automaty ekvivalentní? Pokud ano, jdou
oba redukovat na stejný automat.
Poznámka pod čarou: slovem automat vždy myslíme
námi definovaný konečný deterministický automat.
NKA I.:
Nedeterministický konečný automat
• „Může být najednou ve více stavech.“
• Čím se liší od DKA?
– Může mít méně stavů - snazší návrh i realizace
– Vhodnější pro určité aplikace (vyhledávání)
– Rozdíl je v přechodové funkci
NKA II.:
Definice
• Nedeterministický konečný automat je každá
uspořádaná pětice
A = {Q,∑,δ,q0,F} kde:
– Q je konečná neprázdná množina (stavy)
– ∑ je konečná neprázdná množina (vstupní abeceda)
– δ je přechodová funkce, která ke každé uspořádané
dvojici (q ∈ Q,a ∈ ∑) přiřadí podmnožinu Q
– q0 ∈ Q (počáteční stav)
– F ⊆ Q je konečná množina (rozpoznávací stavy).
NKA III. - příklad
• Automat, který rozpoznává řetězce nul a
jedniček, jež končí sekvencí 01. ∑ = {0,1}
q0 q1 q2q2
0, 1
0 1
NKA III. – srovnání s DKA
q0 q1 q2q2
0, 1
0 1
• Počet vstupů a výstupů se u jednotlivých stavů
nerovná.
• Výpočet někdy „zemře“ – není-li pro daný
vstup definovaný přechod, stav se v dalším
kroce „ruší“.
NKA III. –definice δ tabulkou
q0 q1 q2q2
0, 1
0 1
0 1
q0 (poč.) {q0, q1} {q0}
q1 {} {q2}
q2 {} {}
Rozšířená přechodová funkce
• Analogicky k DKA:
– Přechodová funkce δ zavedená v definici má jako
vstup stav a právě jeden symbol vstupní abecedy.
– Rozšířená přechodová funkce δ* má jako vstup
stav a slovo sestavené nad vstupní abecedou.
Výstupem je opět podmnožina Q.
Jazyk a NKA
• Neformálně: Automat rozpoznává slovo,
pokud po ukončení vstupu je alespoň v jednom
rozpoznávacím stavu (výpočet „nezemře“).
• Formálně: Je-li A = {Q,∑,δ,q0,F}
nedeterministický konečný automat, potom
jazyk L je přijímán automatem právě tehdy
když:
L = {w; δ*(q0,w)  F  }
Souvislost mezi NKA a DKA
• Věta: Každý jazyk, který lze popsat s pomocí
NKA, lze popsat také s pomocí DKA.
• Důsledek: NKA lze převést na ekvivalentní
DKA.
• V praxi mohou mít i podobný počet stavů, ale
DKA má (většinou) více přechodů.
• Při převodu: kde má NKA n stavů, má
vygenerovaný DKA 2n stavů.
Převod NKA na DKA I.
Podmnožinová konstrukce
Máme automat N = {QN,∑,δN,q0,FN}
Hledáme automat D = {QD,∑,δD,q0,FD}
1. QD je množina všech podmnožin QN
2. FD je množina podmnožin QN, takových, že
obsahují alespoň jeden koncový stav automatu
N.
3. Pro každou množinu S z podmnožin QN a pro
každý vstupní symbol definujeme δD
δD(S,a) = p z S δN(p,a)
Převod NKA na DKA II.
0 1
{} {} {}
{q0} {q0, q1} {q0}
{q1} {} {q2}
{q2} {} {}
{q0, q1} {q0, q1} {q0,q2}
{q0, q2} {q0, q1} {q0}
{q1, q2} {} {q2}
{q0,q1,q2} {q0, q1} {q0,q2}
Převod NKA na DKA III.
q1q0
q01
q02
q2
q12
q012{}
Převod NKA na DKA IV.
q0
q01
q02
q1q0
q0
1
q0
2
q2
q1
2
q0
12
{}
Užití NKA
• Vyhledávání: automat, který rozpozná určitá
klíčová slova
• Příklad: NKA, který rozpozná slova mes a myš:
Q0
Q2Q1 Q3
Q4 Q5 Q6
m
e s
m
y š
∑