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, gramatiky a složitost, 26.9.2016 1/21 Příklad a zápis tabulkou IB102 Automaty, gramatiky a složitost, 26.9.2016 2/21 Zápis grafem IB102 Automaty, gramatiky a složitost, 26.9.2016 3/21 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, gramatiky a složitost, 26.9.2016 4/21 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, gramatiky a složitost, 26.9.2016 5/21 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, gramatiky a složitost, 26.9.2016 6/21 Důkaz. Nechť M = (Q, Z, 5, Qo, O- Pak -M' definujeme předpisem M; = (Ou {p}, Z,č', Q0, F), kde p 0 Q a <5'(g, a) = a) je-li 5(q, 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 M'. m M aMř jsou ekvivalentní - dokážeme. IB102 Automaty, gramatiky a složitost, 26.9.2016 7/21 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, gramatiky a složitost, 26.9.2016 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, gramatiky a složitost, 26.9.2016 9/21 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, gramatiky a složitost, 26.9.2016 10/21 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-\ = (Qi,Z,5uqu F), M2 = (Q2,S2,q2, F2) a přechodové funkce ô-\, ô2 jsou totální. Definujeme D FA M3 = (Q3,51,<53, q3l F3), kde ■ Q3 = d x Q2 = {(p, g) I p e d, q e Q2} ■ F3 = F1xF2 = {(p, g) | p e F,, q e F2} ■ 03 = (<7i, H^,q2),v) = {r,s) a S3({r,s),a) = (p,q) S-iiquv) = r a S2(q2,v) = s a 5^(r,a) = p a S2(s,a) = q ^ (Qi, i/a) = p a va) = <7 IB102 Automaty, gramatiky a složitost, 26.9.2016 12/21 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, gramatiky a složitost, 26.9.2016 13/21 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, gramatiky a složitost, 26.9.2016 Limity konečných automatu L = {anbn | n > 0} = {e, ab, aabb. aaabbb. aaaabbbb...} aaaaabbbbb IB102 Automaty, gramatiky a složitost, 26.9.2016 15/21 Předpokládejme, že existuje automat M přijímající jazyk L Nechť M má k stavů. Uvažme výpočet M na slově anbn kde n > k. aaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbb Protože n > k, musí existovat (z Dirichletova principu) stav p takový, že při čtení iniciální posloupnosti symbolů a projde automat stavem p (alespoň) dvakrát. IB102 Automaty, gramatiky a složitost, 26.9.2016 16/21 aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb Platí 5(q0,x)=p S(p,y)=p 8{p,z) = reF Pak ale ô(q0,xz) = ô(ô(q0,x),z) = S(p,z) = r e F aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb IB102 Automaty, gramatiky a složitost, 26.9.2016 17/21 Analogicky můžeme „vsunout" slovo y: Hqo,xyyyz) = š($(š(kä(qo,x),y),y),y),z) = ô(š(s(š(p,ylyly),z) = 6(s(s(p, y), y), z) = S($(p,y),z) = 8(p,z) = re F IB102 Automaty, gramatiky a složitost, 26.9.2016 18/21 Lemma, [o vkládání, pumping lemma] Nechť /_je regulární jazyk. Pak existuje n g N takové, že libovolné slovo w e L délky alespoň n lze psát ve tvaru w = xyz, kde \xy\ < n, y ^ e a xy'z e L pro každé / g N0. Důkaz. Nechť DFA M = (Q, Z, 5, Qo> O rozpoznává jazyk L Položme n = card(Q). Pro libovolné slovo 1/1/ g /- délky alespoň n platí, že automat M projde při akceptování slova w (alespoň) dvakrát stejným stavem. Slovo w tedy můžeme rozdělit na tři části: w = xyz, kde y^ea $(q0, x) = p, 5(p, y) = p a 5(p, z) = r g F. Je zřejmé, že ke zopakování nějakého stavu dojde nejpozději po zpracování prvních n znaků a tedy dostáváme \xy\ < n. Dále S(p,y') = p pro libovolné / g N0, proto také ô(q0,xy'z) = r, tj. xy'z g L(A^) pro každé / g N0. □ IB102 Automaty, gramatiky a složitost, 26.9.2016 19/21 /_je regulární 3A7GN. Vi/i/ g L . ( i/l/l > A7 3x, y, z . ( w = xyz a y/e a V/>0.xy'ze/_)) xy| < n a Pomocí Lemmatu lze dokázat, že nějaký jazyk není regulární. Nechť pro jazyk L platí: ■ pro libovolné n g N ■ existuje takové slovo w e L délky alespoň n, pro které platí, že ■ při libovolném rozdělení slova w na takové tři části x, y, z, že |xy| < n a y ^ e, ■ existuje alespoň jedno / g N0 takové, že xy'z 0 L Pak z Lemma o vkládání plyne, že L není regulární. IB102 Automaty, gramatiky a složitost, 26.9.2016 20/21 Príklad důkazu ne-regularity pomocí Lemmatu o vkládání L = {ucmuR | u e {a, Ď}*, m > 0} IB102 Automaty, gramatiky a složitost, 26.9.2016 21/21