Konečné automaty Definice 1. Konečný automat (Finite Automaton, FA) A4 je pětice (Q,X,ö,q0,F), kde • Q je neprázdná konečná množina stavů. • S je konečná vstupní abeceda. • ô : QxS^Qje parciální přechodová funkce. • Qo £ Q je počáteční (iniciální) stav. • F C Q je množina koncových (akceptujících) stavů. IB102 Automaty a gramatiky, 5.10. 2009 1 Příklad a zápis tabulkou IB102 Automaty a gramatiky, 5.10.2009 2 Zápis grafem IB102 Automaty a gramatiky, 5.10.2009 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) = g pro každý stav g G Q. {^ ^ ^ 5(5(g,^),a) je-li S(q,w) i 5(5(g,^),a) definováno, _L jinak. /\ Slovo w je akceptováno automatem Ai právě když 5(g0,^) £ F. Slovo tu je zamítáno automatem Ai právě když ö(qo,w) 0 F. IB102 Automaty a gramatiky, 5.10.2009 4 Jazyk prijímaný (akceptovaný, rozpoznávaný) automatem A4 je L(M) = {we£* I ö(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 A4 a A4' jsou ekvivalentní, pokud L (A4) = L(Mf). IB102 Automaty a gramatiky, 5.10.2009 5 Parcialita přechodové funkce Přechodová funkce 5 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 FA A4 existuje ekvivalentní FA A4' s totální přechodovou funkcí. Idea důkazu IB102 Automaty a gramatiky, 5.10.2009 6 Důkaz. Necht M = (Q, E, ô, q0, F). Necht automat Ať je definován předpisem M' = {QU{p}^5'^F), kdep^Qa , \ö(q,a) je-li 5(g, 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 • Aí a Ať jsou ekvivalentní- dokážeme. IB102 Automaty a gramatiky, 5.10.2009 Indukcí k délce slova ověříme, že pro každé q G Q a w G S* platí ö(q,w) je-li ö(q,w) definováno, o'{q,w) = { .. , p jinak. Jelikož p £ F, platí L (M) = L(M'). □ IB102 Automaty a gramatiky, 5.10.2009 8 Konstrukce konečných automatů Máme za úkol sestrojit automat rozpoznávající jazyk L = {w £ {a, &}* | 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, 5.10.2009 9 Příklad , &}* I w obsahuje podslovo abaa A (w = 6 V w začína i končí na a a mezi dvěma výskyty b je alespoň jedno a)} a gramatiky, 5.10.2009 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 = (Qu^,ôi,qi,F1), M2 = (Q2^62,q2,F2) a přechodové funkce 61,62 jsou totální. Definujeme FA M3 = (<53,S, 63^3,F3), kde • Q3 = Qi x Q2 = {(p, q) \peQi,qe Q2} • F3 = F1xF2 = {(p, q)\peF1,qeF2} • 43 = (?1,Í2) • Í3((p,?),a) = (5i(p,a),$2(g,a)) Tvrzení: L(A43) = L(Mi) n L(A42) IB102 Automaty a gramatiky, 5.10.2009 11 Důkaz. Nejprve dokážeme toto tvrzení: 53((gi,g2),w) = (p,g) ^^ či(9i?w) =p A52(92,w) = 9 Důkaz se provede indukcí vzhledem k w Základní krok \w\ = 0: Z definice 53((9i? 92), e) = (91,92), 5i(9i?e) = 91- $2(92, e) = 92 Pro w = e je tedy ekvivalence platná. Indukční krok: Necht w = va, kde i; G S*, a G S. Platí: S((9i?92),va) = (P, 9) ^^ 53((9i,92),^) = (r, 5) A 53((r,s),a) = (p,g) «=> 5i(gi, ?;) = r A #2(92, v) = s Aíi(r,a)=p A 52(s, a) = q <=> 5i(gi,?;a)=p A ö2(q2,va) = q IBIO2 Automaty a gramatiky, 5.10.2009 12 Nyní již lze snadno dokázat vlastní tvrzení věty: w G L(M3) ^^ ^((qu 92), w) = (p, g) kde p G Fi a g G F2 ^^ 5i(