Konečné automaty
Definice 1. Deteministický konečný automat (Deterministic Finite Automatem, DFA) M je pětice (Q, E, 5, go? F), kde
• Q je neprázdna konečná množina stavů.
• E je konečná vstupní abeceda.
• ô : Q x E —)► Q je parciální přechodová funkce.
• Qo £ Q Je počáteční (iniciální) stav.
• ^ ^ Q je množina koncových (akceptujících) stavů.
IB102 Automaty a gramatiky, 24.10. 2012 1
klad a zápis tabulkou
Zápis grafem
IB102 Automaty a gramatiky, 24.10.2012
3
Výpočet konečného automatu
Rozšířená přechodová funkce 5: Q x E* —> Q je parciální funkce definovaná induktivně vzhledem k délce slova ze £*:
• 8(Qič) = Q Pro každý stav q G Q.
8(q,wa) =
Í6(5(q, w),a) je-li 8{q,w) i 5(<5(g, w),a) definováno, _L jinak.
Slovo w je akceptováno automatem A4 právě když ô(qo,w) G F
/\
Slovo w je zamítáno automatem A4 právě když 5(go, w) 0 F.
IB102 Automaty a gramatiky, 24.10.2012
Jazyk přijímaný (akceptovaný, rozpoznávaný) automatem M, je
L{M) = {w G E* | 6(q0,w) G F}.
Jazyk, který je rozpoznatelný (nějakým) deterministickým konečným automatem, nazveme regulárni.
Ekvivalenci deterministických podobně jako v případě gramatik: pokud L(M) = L(M').
konečných automatů definujeme automaty M a M! jsou ekvivalentní,
IB102 Automaty a gramatiky, 24.10.2012
5
Parcialita přechodové funkce
Přechodová funkce ô zavedena jako parciální.
Parcialita přechodové funkce nemá podstatný vliv na výpočetní sílu konečných automatů.
Lemma 1. Ke každému DFA A4 existuje ekvivalentní DFA M! s totální přechodovou funkcí.
Idea důkazu
a
IB102 Automaty a gramatiky, 24.10.2012
6
Důkaz. Necht M = (Q, E, ô, q0, F). Necht automat Mr je definován předpisem
M' = (Q U {p}, E, ď, go, F), kde p 0 Q a
(S(q,a)   je-li %, a) definováno, Ip jinak.
Zejména 5'(p, a) — p pro každé a G E. Důkaz korektnosti:
• Ať má totální přechodovou funkci - zřejmé z definice .A/ť.
• Ai a .A/ľ jsou ekvivalentní - dokážeme.
IB102 Automaty a gramatiky, 24.10.2012
7
Indukcí k délce slova ověříme, že pro každé q G Q a w G E* platí
ô'(q, w) =
ô(q,w) je-li ô(q,w) definováno, p jinak.
Jelikož p   F, platí = D
IB102 Automaty a gramatiky, 24.10.2012
8
Konstrukce konečných automatů
Máme za úkol sestrojit automat rozpoznávající jazyk
L = {w G | w obsahuje podslovo abaa}
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, 24.10.2012
9
Příklad
{w G | w obsahuje podslovo abaa
A (w = b V w začíná i končí na a a mezi dvěma výskyty b je alespoň jedno a)}
IB102 Automaty a gramatiky, 24.10.2012
10
Synchronní paralelní kompozice automatů
Pro dané automaty M.\ a Ai2 umožňuje sestrojit automat rozpoznávající průnik (sjednocení, rozdíl) jazyků L{M\) a L{M2).
Necht Mi = (Qli'Ľiô1,qliF1), M2 = (Q2,X,62,q2,F2) a přechodové funkce 81,82 jsou totální.
Definujeme DFA M3 = (Qs,^,h,Q3,Fs), kde
• Qs = Qi x Q2 = {(p, g) I p G Qi, g G Q2}
• F3 = F1xF2 = {(p, g) I P G i7!, g G F2}
• 93 = (gi,g2)
• ^3((p,g),a) = (<Ji(p,a),<52(g,a)) Tvrzení: L(M3) = L(Mi) n L(M2)
IB102 Automaty a gramatiky, 24.10.2012
11
Důkaz. Nejprve dokážeme toto tvrzení:
Ô3((qiiQ2),w) = (p,q) ô1(q1,w)=pAô2(q2,w) = q
Důkaz se provede indukcí vzhledem k \w
• Základní krok \w\ — 0:
Z definice 8^{{q1,q2),e) = (qi,q2), h{qi,s) = qi, S2(q2,s) = 92-Pro w = e je tedy ekvivalence platná.
• Indukční krok: Necht w = va, kde ^ G E*, a G E. Platí:
S((íi,í2),va) = (p,g)
h{{qi,q2),v) = {r,s) A (J3((r,s),a) = (p,qr) <í=>
v) = ^ A 52(g2, v) = 5 A 5i(r,a) = _p A 52(s,a) = q fi(gi,va)=p A 52(q2,va)=q
IB102 Automaty a gramatiky, 24.10. 2012 12
Nyní již lze snadno dokázat vlastní tvrzení věty:
w G L(M3)
Q2),w) = (p, g) kde p G Fx a g G F2 <fi(gi, tu) =p A S(?2,w) = g
w; G nL(A^2). □
Modifikace pro sjednocení, tj. £(^3) = L(A^i) U L{M.2)'-
DÚ: Modifikujte konstrukci tak, aby platilo L(Ms) = L(Mi)\L(M2)-
IB102 Automaty a gramatiky, 24.10. 2012 13
Automat pro komplement
K automatu M = (Q, E, 5, go? ^) s totální přechodovou funkcí sestrojíme automat .A/í rozpoznávající jazyk co-L(M) jako
IB102 Automaty a gramatiky, 24.10.2012
14