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, ■ go £ O je počáteční (iniciální) stav, ■ ^ Q Q je množina koncových (akceptujících) stavů. IB102 Automaty, gramatiky a složitost, 5.10.2015 1/21 Příklad a zápis tabulkou IB102 Automaty, gramatiky a složitost, 5.10.2015 2/21 Zápis grafem IB102 Automaty, gramatiky a složitost, 5.10.2015 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), a) je-li 5(qr, w) i 5(5(q, w), a) 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, 5.10.2015 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, 5.10.2015 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, 5.10.2015 6/21 Důkaz. Nechť M = (Q, 51, 5, q0, F). Pak M' definujeme předpisem M; = (Ou {p}, Z,č', gb, F), kde p £ Q a <5'(g, a) = a) je-li S(q, a) definováno, p jinak. Zejména 5'(p, a) = p pro každé a g Z. 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, 5.10.2015 7/21 Indukcí k délce slova ověříme, že pro každé g e Q a w e Z* platí 5(q, w) je-li 5(q, w) definováno, p jinak. Jelikož p £ F, platí L(M) = L{Mf). IB102 Automaty, gramatiky a složitost, 5.10.2015 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, 5.10.2015 9/21 Příklad {w e {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, 5.10.2015 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-\ = (Oi, Z, 5i, qfi, F|), .M2 = (Q2, Z, 52, 92, ^2) a přechodové funkce <5i, S2 jsou totální. Definujeme D FA M3 = (03, Z, <53, q3, F3), kde ■ 03 = Q, x 02 = {(p, qr) I p g d, qf e Q2} ■ F3 = F-\ x F2 = {(p,g) | p g F-\,q e F2} ■03 = (<7i, Q2) ■ <%((p, q), a) = (5i (p, a), 52(g, a)) Tvrzení. L(M3) = L(M^n L{M2) IB102 Automaty, gramatiky a složitost, 5.10.2015 11/21 Důkaz. Nejprve dokážeme toto tvrzení: ô3((q1,q2),w) = (p,q) ^ ^(q^, w) = pAô2(q2, w) = q Důkaz se provede indukcí vzhledem k \ w ■ Základní krok |w| = 0: Z definice S3((q^, q2), e) = , q2), ^ , e) = ^, S2{q2, e) = q2. Pro w = e je tedy ekvivalence platná. ■ Indukční krok: Nechť w = va, kde v e Z*, a e Z. Platí: 53((qi,q2),va) = (p,q) <=;> 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 ^ , i/a) = p A 82{q2l va) = q IB102 Automaty, gramatiky a složitost, 5.10.2015 12/21 Nyní již lze snadno dokázat vlastní tvrzení věty: w e L{M3) 53{{q^q2),w) = (p,q) kdepe FA aq e F2 ^ 0} = {e, ab. aabb. aaabbb. aaaabbbb...} aaaaabbbbb IB102 Automaty, gramatiky a složitost, 5.10.2015 15/21 Předpokládejme, že existuje automat M přijímající jazyk L Nechť 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, 5.10.2015 16/21 aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb Platí 5(q0,x)=p 5(p,y)=p S(p7z) = reF Pakale ô(q0,xz) = ô(ô(q0,x),z) = 5(p,z) = r e F aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb IB102 Automaty, gramatiky a složitost, 5.10.2015 17/21 Analogicky můžeme „vsunout" slovo y: S(Qo,xyyyz) = S(S(S(5(5(q0,x),y),y),y),z) = 6(S(5(p,y),ylz) = S(S(p,y),z) = S{p,z) = reF IB102 Automaty, gramatiky a složitost, 5.10.2015 18/21 Lemma, [o vkládání, pumping lemma] Nechť Z. 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 w g Z. 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,yi) = p pro libovolné / g N0, proto také S(q0,xyiz) = r, tj. xy'z g Z-(.M) pro každé / g N0. □ IB102 Automaty, gramatiky a složitost, 5.10.2015 19/21 Z-je regulární Vl/1/ G /. . ( i/i/l > n 3x, y, z . (1/1/ = xyz A y/e A V/>0.xy'zG/-)) 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 g 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| < r? a y £, ■ existuje alespoň jedno / g N0 takové, že xy'z ^ L. Pak z Lemma o vkládání plyne, že L není regulární. IB102 Automaty, gramatiky a složitost, 5.10.2015 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, 5.10.2015 21/21