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, 25.9.2017
1/14
Příklad a zápis tabulkou
IB102 Automaty a gramatiky, 25.9.2017
2/14
Zápis grafem
IB102 Automaty a gramatiky, 25.9.2017
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, 25.9.2017 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, 25.9.2017
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, 25.9.2017
6/14
Důkaz. Nechť M = (Q, 51,5, cfo, F). Pak M' definujeme předpisem
M/ = (Ou {p},Z,5', g0, F), kde p ^ Q a
6'{q, a) =
a) je-li a) definováno p jinak.
Zejména 5'(p, a) = p pro každé a e 51.
Důkaz korektnosti:
■ Ať má totální přechodovou funkci - zřejmé z definice Ml m M a Mf jsou ekvivalentní - dokážeme.
IB102 Automaty a gramatiky, 25.9.2017
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, 25.9.2017
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, 25.9.2017
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, 25.9.2017 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, 25.9.2017
11/14
Důkaz. Nejprve dokážeme toto tvrzení:
š((<Jh > <fc),    = (P, Q) S\(ch,w) = pA52(ck,w) = q
Důkaz se provede indukcí vzhledem k \ w
■ Základní krok \ w\ =0:
Z definice S3((ch, q2), e) = (q,, q2), 5i (Qi, e) = <7i, S(<fc, e) = <k-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) «
S((<7i, 92), v) = (/*, 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Í (Qi, va) = p a S(q2, va) = q
IB102 Automaty a gramatiky, 25.9.2017
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, 25.9.2017
13/14
Automat pro komplement
K automatu M = (Q, Z, S, q0, F) s totální přechodovou funkcí
sestrojíme automat M rozpoznávající jazyk co-L(M) jako
M = (Q,Z,S,qo,Q\F).
IB102 Automaty a gramatiky, 25.9.2017