Konečné automaty
Definice. Deterministický konečný automat (Deterministic Finite Automaton, D FA) M je pětice (Q, Z, S, q0, F), kde
■ Q je neprázdná konečná množina stavů,
■ Z je konečná vstupní abeceda,
■ á:OxZ^Qje parciální přechodová funkce,
■ Qo £ O je počáteční (iniciální) stav,
■ F c Q je množina koncových (akceptujících) stavů.
IB102 Automaty a gramatiky, 23.9.2019
1/14
Příklad a zápis tabulkou
IB102 Automaty a gramatiky, 23.9.2019
2/14
Zápis grafem
IB102 Automaty a gramatiky, 23.9.2019
3/14
Výpočet konečného automatu
Rozšířená přechodová funkce S : Q x Z* Q je parciální funkce definovaná induktivně vzhledem k délce slova ze Z*:
■ 5(q, s) = q pro každý stav q e Q
5{q, wa) =
w), á) je-li      w) i 5(5(q, w), á) definováno _L jinak
Slovo w\e akceptováno automatem M právě když S(q0, w) e F. Slovo w\e zamítáno automatem M právě když S(q0, w) ^ F.
IB102 Automaty a gramatiky, 23.9.2019 4/14
Jazyk přijímaný (akceptovaný, rozpoznávaný) automatem M je
L(M) = {w g 51* | ô(q0,w) g F}.
Jazyk, který je rozpoznatelný (nějakým) deterministickým konečným automatem, nazveme regulárni.
Automaty M a M' nazveme ekvivalentní, právě když L(M) = L(M').
IB102 Automaty a gramatiky, 23.9.2019
5/14
Parcialita přechodové funkce
Přechodová funkce S byla zavedena jako parciální. Parcialita přechodové funkce nemá podstatný vliv na výpočetní sílu konečných automatů.
Lemma. Ke každému DFA M existuje ekvivalentní DFA M' s totální přechodovou funkcí.
Idea důkazu:
IB102 Automaty a gramatiky, 23.9.2019
6/14
Důkaz. Nechť M = (Q, 51, S, q0l F). Pak Mr definujeme předpisem
M' = (Q u {p}, Z,   qb, F), kde p 0 Q a
a) =
5(g, a) je-li a) definováno, p jinak.
Zejména5'(p,a) = ppro každé aeL
Důkaz korektnosti:
■ M! má totální přechodovou funkci - zřejmé z definice Ať.
■ M a Ať jsou ekvivalentní - dokážeme.
IB102 Automaty a gramatiky, 23.9.2019
7/14
Indukcí k délce slova ověříme, že pro každé g e Q a 1/1/ e Z* platí
5(q, w) je-li 5(q, w) definováno, p jinak.
Jelikož p 0 F, platí L(A4) = L(Mř).
IB102 Automaty a gramatiky, 23.9.2019
Konstrukce konečných automatů
Máme za úkol sestrojit automat rozpoznávající jazyk
L = {w g {a, by | w obsahuje podslovo abaa}
Označení stavů automatu zvolíme tak, aby bylo patrné, jaká část požadovaného podslova abaa\\ž byla automatem přečtena:
IB102 Automaty a gramatiky, 23.9.2019
9/14
Příklad
{w g {a, £>}* | w obsahuje podslovo abaa a (w = b v w začíná i končí
na a a mezi dvěma výskyty b je vždy alespoň jedno a)}
	©	©	©	©	©
©	©	©	©	©	©
0	©	©	©	©	©
©	©	©	©	©	©
©	©	©	©	©	©
IB102 Automaty a gramatiky, 23.9.2019 10/14
Synchronní paralelní kompozice automatů
Pro dané automaty M\ a M2 umožňuje sestrojit automat rozpoznávající průnik (sjednocení, rozdíl) jazyků L{M\) a L(M2)-
Nechť M-\ = {Q-\,Y.,S-\,q-\, F,), M2 = (Q2,S2,q2, F2) a přechodové funkce <5i, S2 jsou totální.
Definujeme D FA M3 = (03,51, <53, q3, F3), kde
■ Q3 = d x Q2 = {(p, q) | p g Qi, g e Q2}
■ F3 = F| x F2 = {(p, g) | p e F, g e F2}
■ q3 = (<7l,<fe)
■ <%((p, q), a) = (íi (p, a), <J2(qr, a)) Tvrzení. L(M3) = L(M)n L(AÍ2)
IB102 Automaty a gramatiky, 23.9.2019
11/14
Důkaz. Nejprve dokážeme toto tvrzení:
š((<Jh><fc),    = (P,Q) 5-l(q^w)=pAÔ2(q2,w) = q
Důkaz se provede indukcí vzhledem k \ w
■ Základní krok \ w\ = 0:
Z definice 4((<7i, <k),e) = (<7i><fc). í (<7i, e) = Qi. S(q2, e) = q2-Pro iv = e je tedy ekvivalence platná.
■ Indukční krok: Nechť w = va, kde v e T.*, a e Z. Platí: 83((qi,q2),va) = {p,q)
S3((q1,q2),v) = (r,s) a S3({r, s), a) = (p, q)
S-i(quv) = r a 82{q2,v) = s a 51(r,a)=p a <S2(s,a) = <7 «
5Í (qri, va) = p a ô2(q2, va) = q
IB102 Automaty a gramatiky, 23.9.2019
12/14
Nyní již lze snadno dokázat vlastní tvrzení věty:
w e L{M3)
53{{q^q2),w) = (p,q) kdepe FA aqe F2 ^ £i(q^w) = pA62{q2,w) = q ^
we L(M^nL(M2) □
Modifikace pro sjednocení, tj. L{M3) = L(M^) u L(Mz)\
DÚ: Modifikujte konstrukci tak, aby platilo L(M3) = L(M^ \ /-(A^)-
IB102 Automaty a gramatiky, 23.9.2019
13/14
Automat pro komplement
K automatu M = (Q, Z, 5, g0j0 s totální přechodovou funkcí
sestrojíme automat M rozpoznávající jazyk co-L(M) jako
A^ = (Q,Z,(J,qb,Q\F).
a
IB102 Automaty a gramatiky, 23.9.2019