Konečné automaty Definice. Deterministický konečný automat (Deterministic Automaton, DFA) 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, ■ č:QxZ->Qje parciální přechodová funkce, ■ q0 e Q 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, 22.9.2014 Příklad a zápis tabulkou IB102 Automaty, gramatiky a složitost, 22.9.2014 2/21 Zápis grafem IB102 Automaty, gramatiky a složitost, 22.9.2014 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*: ■ S(q, e) = q pro každý stav q g Q (ô (ô (q, w), ä) je-li ô(q, w) i ô(ô(q, w), ä) definováno _L jinak Slovo w\e akceptováno automatem M právě když Š(q0, w) g F. Slovo wje zamítáno automatem M právě když Š(q0, w) 0 F. IB102 Automaty, gramatiky a složitost, 22.9.2014 4/21 Jazyk přijímaný (akceptovaný, rozpoznávaný) automatem M je L(M) = {w g Z* | ô(qo,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, 22.9.2014 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: a a a IB102 Automaty, gramatiky a složitost, 22.9.2014 6/21 Důkaz. Nechť M = (Q, 51, ô, q0, F). Pak M' definujeme předpisem M' = (Qu {p}, Z, <$', qr0, F), kde p 0 Q a ô'(q,a) 6(q, a) je-li t)(qr, a) definováno, p jinak. Zejména S'(p, a) = p pro 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, gramatiky a složitost, 22.9.2014 7/21 Indukcí k délce slova ověříme, že pro každé q e Q a w e Z* platí S(q, w) je-li <5(g, w) definováno, p jinak. Jelikož p 0 F, platí /.(Aí) = /.(Ať)- S'{q, w) IB102 Automaty, gramatiky a složitost, 22.9.2014 Konstrukce konečných automatů Máme za úkol sestrojit automat rozpoznávající jazyk L = {w g {a, b}* | 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, 22.9.2014 9/21 Příklad {w £ {a, b}* | w obsahuje podslovo abaa A (w = b v w začíná i končí na a a mezi dvěma výskyty b\e vždy alespoň jedno a)} © © © © © ® ® © 0 © © © © © © © © © © © © © © © © © IB102 Automaty, gramatiky a složitost, 22.9.2014 10/21 Synchronní paralelní kompozice automatů Pro dané automaty M i a M2 umožňuje sestrojit automat rozpoznávající průnik (sjednocení, rozdíl) jazyků L(M-\) a L(M2). Nechť M<\ = (Q^,T,ôi,qi, ), M2 = (Q2,ô2,q2, F2) a přechodové funkce 6^, S2 jsou totální. Definujeme D FA M3 = (Q3, Z, <53, q3, F3), kde ■ Q3 = d x Q2 = {(p, g) I p G d, g G Q2} ■ F3 = F, x F2 = {(p, qr) | p G F, qr G F2} ■ 93 = (91,%) ■ <53((p, q), a) = (p, a), č2(qr, a)) Tvrzení. L(.M3) = L{M,) n L(.M2) IB102 Automaty, gramatiky a složitost, 22.9.2014 11/21 Důkaz. Nejprve dokážeme toto tvrzení: S3((qA,q2),w) = (p,q) <=^ ô\(ch,w) = p/\S2(q2,w) = Důkaz se provede indukcí vzhledem k \ w\. m Základní krok \ w\ =0: Z definice S3((qA, q2),e) = (Qi, q2), S\(gi,s) = qi, S2(q2,e) = Pro w = e je tedy ekvivalence platná. ■ Indukční krok: Nechť w = va, kde v e Z*, a e Z. Platí: ó3{{qi,q2),va) = {p,q) <=^> 53{{q:,q2),v) = (r,s) A ó3{{r,s),a) = (p,q) <=^ SA(qA,v) = r A S2(q2, v) = s A ^(r, a) = p A 62{s, a) = q SA (qA ,va)=p A S2(q2, va) = q IB102 Automaty, gramatiky a složitost, 22.9.2014 Nyní již lze snadno dokázat vlastní tvrzení věty: w g L(M3) ř2)- IB102 Automaty, gramatiky a složitost, 22.9.2014 13/21 Automat pro komplement K automatu M = (Q, Z, 5, q0, F) s totální přechodovou funkcí sestrojíme automat M rozpoznávající jazyk co-L(M) jako M = (Q,T,5,q0,Q\F). IB102 Automaty, gramatiky a složitost, 22.9.2014 14/21 Limity konečných automatů L = {anbn | n > 0} = {e, ab, aabb, aaabbb, aaaabbbb...} aaaaabbbbb IB102 Automaty, gramatiky a složitost, 22.9.2014 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, 22.9.2014 16/21 aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb Platí S(q0,x)=p ô(p,y)=p S(p,z) = reF Pakale S(q0,xz) = S(S(q0,x),z) = S(p,z) = reF aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb IB102 Automaty, gramatiky a složitost, 22.9.2014 17/21 Analogicky můžeme „vsunout" slovo y: 6{- 3/7 g N. Vw g L . (\w\ > n =>- 3x,y,z . (w = xyz a y/e a \xy\ < n a V/ > O . xy'z g L)) Pomocí Lemmatu lze dokázat, že nějaký jazyk není regulární. Nechť pro jazyk L platí: ■ pro libovolné neN ■ existuje takové slovo w e L délky alespoň /i, pro které platí, že ■ při libovolném rozdělení slova w na takové tři části x, y, z, že |xy| < nay/ 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, 22.9.2014 20/21 Příklad důkazu ne-regularity pomocí Lemmatu o vkládání L = {ucmuR | u e {a, b}*, m > 0} IB102 Automaty, gramatiky a složitost, 22.9.2014 21/21