Konečné automaty
Definice 1. Deteministický konečný automat (Deterministic Finite Automaton, DFA) M je pětice (Q, S, 5, qo,F), kde
• Q je neprázdna konečná množina stavů.
• S je konečná vstupní abeceda.
• 5 : QxS^Qje parciální přechodová funkce.
• Qo £ Q Je počáteční (iniciální) stav.
• i7" ^ Q je množina koncových (akceptujících) stavů.
IB102 Automaty a gramatiky, 26.10. 2011 1
Příklad a zápis tabulkou
IB102 Automaty a gramatiky, 26.10. 2011
2
Zápis grafem
IB102 Automaty a gramatiky, 26.10. 2011
3
Výpočet konečného automatu
Rozšírená přechodová funkce S: Q x S* —> Q je parciální funkce definovaná induktivně vzhledem k délce slova ze S*:
• S(q,e) = q pro každý stav q G Q.
S(q1 wa) —
S(S(q,w),a) je—li S(q,w) i S(S(q,w),a) definováno, _L jinak.
Slovo w je akceptováno automatem M právě když 5(go, w) G F Slovo ii; je zamítáno automatem M právě když S(qo,w) ý. F.
IB102 Automaty a gramatiky, 26.10. 2011
Jazyk přijímaný (akceptovaný, rozpoznávaný) automatem Ai je
L(M) = {w G S* | ô(q0,w) G F}.
Jazyk, který je rozpoznatelný (nějakým) konečným automatem, nazveme regulární.
Ekvivalenci konečných automatů definujeme podobně jako v případě gramatik: konečné automaty Ai a M* jsou ekvivalentní, pokud L(A4) — L(M').
IB102 Automaty a gramatiky, 26.10. 2011
5
Parcialita přechodové funkce
Přechodová funkce ô zavedena jako parciální.
Parcialita přechodové funkce nemá podstatný vliv na výpočetní
konečných automatů.
Lemma 1. Ke každému DFA Ai existuje ekvivalentní DFA s totální přechodovou funkcí.
Idea důkazu
a
IB102 Automaty a gramatiky, 26.10. 2011
Důkaz. Necht M = (Q,X,ô,q0,F). Necht automat M1 je definován předpisem
M! = (QU{p},X,ô',q0,F), kdepČQ a
6'(q, a) =
S(q,a) je-li S(q,a) definováno, p jinak.
Zejména 5'(p, a) — p pro každé a G S.
Důkaz korektnosti:
• „A/ľ má totální přechodovou funkci - zřejmé z definice Aif.
• A4 a A4' jsou ekvivalentní - dokážeme.
IB102 Automaty a gramatiky, 26.10. 2011
7
Indukcí k délce slova ověříme, že pro každé q G Q a w G £* platí
<5'(g,iy) =
5(q,w) je-li 5(q,w) definováno, p jinak.
Jelikož p £ F, platí L(M) = D
IB102 Automaty a gramatiky, 26.10. 2011
8
Konstrukce konečných automatů
Máme za úkol sestrojit automat rozpoznávající jazyk
L — {w £ {a, 6}* | ii; obsahuje podslovo afraa}
Označení stavů automatu zvolíme tak, aby bylo patrné, jaká část požadovaného podslova abaa již byla automatem přečtena:
IB102 Automaty a gramatiky, 26.10. 2011
9
Příklad
{w £ {a, 6}* | w obsahuje podslovo abaa
IB102 Automaty a gramatiky, 26.10. 2011
A (w — b V w začíná i končí na a a mezi dvěma výskyty b je alespoň jedno a)}
10
Synchronní paralelní kompozice automatů
Pro dané automaty Mi a M2 umožňuje sestrojit automat rozpoznávající průnik (sjednocení, rozdíl) jazyků L(Mi) a L(M2)-
Necht Mi = (Qi,S,(Ji,^i,Fi), M2 = (Q2,£,<52,(72,F2) a přechodové funkce 61,62 jsou totální.
Definujeme DFA M3 = (Q3, S, S3, <?3, F3), kde
• Q3 = Qi x Q2 = {(p, g) I p g Qi, g g Q2}
• F3 = Fi x F2 = {(p, g) I p g Fi, q g F2}
• Qs = (<7i,42)
• č3((p,g),a) = (6i(p,a),62(q,a)) Tvrzení: L(M3) = L{Mi) n L(M2)
IB102 Automaty a gramatiky, 26.10. 2011
11
Důkaz. Nejprve dokážeme toto tvrzení:
> 5i(qi,w) =p Aá2(92,^) = q
Důkaz se provede indukcí vzhledem k w .
• Základní krok \w
0:
Z definice 63((q1,q2),e) = (91,^2), S^q^e) = qlt 52(q2,e) = #2-Pro ii; = e je tedy ekvivalence platná.
• Indukční krok: Necht w = va, kde i; £ E*, a £ E. Platí:
S((tfi,02),wO = (p,q)
£((21,02),^) = (r,s) A <J3((r, s), a) = <í=>
v) = r A 52(92, ^)=5 Aíi(r,a)=|) A 52(s,a) = ? 5i(gi,i;a)=p A 52{q2,va) = q
IB102 Automaty a gramatiky, 26.10. 2011
12
Nyní již lze snadno dokázat vlastní tvrzení věty:
w e L(Ms) ^=>
S3((qu q2),w) = (p, g) kde p e Fx a g e F2 5i(qi,w) = p Aá2(?2,^) = g
w G L(jVíi) nL(jVÍ2)- D Modifikace pro sjednocení, tj. L(Mz) = L(JWi) U L(AÍ2)-
DÚ: Modifikujte konstrukci tak, aby platilo Í/(7W3) = L(Mi)\L(M2).
IB102 Automaty a gramatiky, 26.10. 2011 13
Automat pro komplement
K automatu M = (Q,       qo,F) s totální přechodovou funkcí
sestrojíme automat Ai rozpoznávající jazyk co-L(Ai) jako
M = (Q,X,S,q0,Q\F).
IB102 Automaty a gramatiky, 26.10. 2011
14