Konečné automaty
Definice 1.   Konečný automat (Finite Automaton, FA) M je petice
(Q, S,ô,qo,F), kde
• Q je neprázdna koneCna množina stavU.
• S je koneCna vstupní abeceda.
• ô : Q x S — Q je parcialní prechodova funkce.
• q0 £ Q je poCatečn í (iniciain í) stav.
• F C Q je množina koncových (akceptuj íc ich) stavU.
IB102 Automaty a gramatiky, 27.10.2010
1
Příklad a zápis tabulkou
IB102 Automaty a gramatiky, 27.10.2010
2
Zápis grafem
IB102 Automaty a gramatiky, 27.10.2010
3
Výpočet konečného automatu
Rozšířená přechodová funkce 5: Q x S* — Q je parciální funkce definovana induktivně vzhledem k delce slova ze S*:
• S(q,e) = q pro kaZdý stav q £ Q.
5 \5(S(q,w),a)   je-li S(q,w) i 5(S(q,w),a) definovano,
^ 5(q,wa) = <
_L jinak.
Slovo w je akceptováno automatem M prave kdýZ S(q0, w) £ F. Slovo w je zamítáno automatem M prave kdýZ S(q0, w) £ F.
IB102 Automaty a gramatiky, 27.10.2010
4
Jazyk prijímaný (akceptovaný, rozpoznávaný) automatem M je
L (M) = {w G S* | ô(qo,w) G F}.
Jazyk, ktery je rozpoznatelný (nejakým) konecnym automatem, nazveme regularní.
Ekvivalenci konecnych automatu definujeme podobne jako v případe gramatik: konečne automaty M a M' jsou ekvivalentní, pokud L(M) = L(M7).
IB102 Automaty a gramatiky, 27. 10. 2010
5
Pářcialita přechodové funkce
Prechodova funkce 5 zavedena jako parciainí.
Parcialita prechodove funkce nema podstatný viiv na vypoCetní síiu koneCnych automatu.
Lemma 1. Ke kaZdemu FA M existuje ekvivaientn í FA M s totain í prechodovou funkc í .
Idea dukazu
a
a
IB102 Automaty a gramatiky, 27.10.2010
6
Důkaz. Necht M = (Q, S,ô,q0,F). Necht automat M' je definovan předpisem
M = (Q U {p}, S, ô', qo, F), kde p G Q a
' (ô (q, a)   je-li ô (q, a) definovano,
ô(q,a) = < .. ,
lp jinak.
Zejmena ô '(p, a) = p pro kazde a G S. Důkaz korektnosti:
• M' ma totaln í přechodovou funkci - zrejme z definice M'.
• M a M' jsou ekvivalentn í - dokazeme.
IB102 Automaty a gramatiky, 27. 10. 2010
7
Indukcí k délce slova ověříme, že pro každé q £ Q a w £ S* platí
S(q,w) je-li S(q,w) definováno, p jinak.
Jelikož p £ F, platí L(M) = L(Mf). □
IB102 Automaty a gramatiky, 27.10.2010
8
Konstrukce konečných automatů
Máme za úkol sestrojit automat rozpoznávající jazyk
L = (w G (a, b}* | w obsahuje podslovo abaa]
OznaCení stavú automatu zvolíme tak, aby bylo patrne, jaka Cast pozadovaneho podslova abaa jiz byla automatem preCtena:
IB102 Automaty a gramatiky, 27.10.2010
9
Příklad
{w G {a, 6}* | w obsahuje podslovo abaa
IB102 Automaty a gramatiky, 27.10.2010
A (w = b V w začína i končí na a a mezi dvema 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) jazyku L(M1) a L(M2).
Necht Mi = (Qi, E,5i,qi,Fi), M2 = (Q2, £,<$2,q2,^2) a přechodové funkce 5i,52 jsou totální.
Definujeme FA M3 = (Q3, £,<$3,q3, F3), kde
• Q3 = Qi x Q2 = {(p, q) | p G Qi, q G Q2}
• F3 = Fi x F2 = {(p, q) | p G Fi, q G F2}
^ q3 = (qi ,q2)
Tvrzení: L(M3) = L(Mi) n L(M2)
IB102 Automaty a gramatiky, 27.10.2010
11
Důkaz. Nejprve dokážeme toto tvrzení:
<*3((?i,?2),w) = (p,Q) 51{q1,w) = p A 52(g2,w)= q
Důkaz se provede indukcí vzhledem k |w
• Základní krok |w| = 0:
Z definice 53((qi,q2),e) = (qi,q2), <^i(qi,^) = qi, <^(q2,e) = q2. Pro w = e je tedy ekvivalence platna.
• Indukční krok: Necht w = va, kde v G S*, a G S. Plátí:
ča((qi,q2),va) = (p,q)
,q2),v) = (r,s) A 5a((r,s),a) = ) 6i(qi, v) = r A 62 (q2, v) = s A 6i(r, a) = p A ^2(0, a) = q 6i(qi,va)= p A 62(q2,va) = q
IB102 Automaty á grámátiky, 27.10. 2010 12
Nyn í již lze snadno dokázat vlastn í tvrzen í věty:
č3((qi, 92), w) = (p, q) kde p e Fi a q e F2
S1(q1,w)= p A ^2(92, w)= q <^=>
w e L(Mi) n L(M2). □
Modifikace pro sjednocen í, tj. L(M3) = L(M1) U L(M2):
DÚ: Modifikujte konstrukci tak, aby platilo L(M3) = L(Mi) \L(M2)■
IB102 Automaty a gramatiky, 27-10-2010
13
Automat pro komplement
K automatu M = (Q, S,ô,q0, F) s totaln í prechodovou funkc í
sestrojíme automat M. rozpoznávající jazyk co-L(AÍ) jako
M = (Q, S,ô,qo,Q \ F).
M:
a
M:
a
a
IB102 Automaty a gramatiky, 27. 10. 2010
14