Limity konečných automatů L = {anbn | n > 0} = {č, a&, aa66, aaabbb, aaaabbbb...} aaaaabbbbb IB102 Automaty a gramatiky, 12.10.2009 1 Předpokládejme, že existuje automat A4 přijímající jazyk L. Necht A4 má k stavů. Uvažme výpočet A4 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 a gramatiky, 12.10.2009 2 aaaaaaaa aaaaaaa aaaabbbbbbbbbbbbbbbbbbb Platí /\ ^ ^ %o,x)=p S(p,y)=p 5(p,z) =r e F Pak ale S\ S\ S(qo,xz) = 8{ö(clq,x),z) = 5{p^z) = reF aaaaaaaa aaaabbbbbbbbbbbbbbbbbbb IB102 Automaty a gramatiky, 12.10.2009 Analogicky můžeme "vsunout" slovo y S\ S\ S\ S\ S\ 5(q0,xyyyz) = ö(ö(ö(ö(ö(q0,x),y),y),y),z) S\ S\ S\ S\ = ô(ô(ô(ô(j>,y),y),y),z) S\ S\ S\ = Wfeíl),!/),«) = 5(5(P,Ž/),^) = ô(j>,z) = r e F IB102 Automaty a gramatiky, 12.10.2009 4 Lemma 1. [o vkládání, pumping lemma] Necht L je regulárníjazyk. Pak existuje n G N takové, že libovolné slovo w G L délky alespoň n lze psát ve tvaru w = xyz, kde \xy\ < n, y ^ e a xylz G L pro každé i G No- Důkaz. Necht FA Aí = (Q, E, 5, go? ^) rozpoznává jazyk L. Položme n = card(Q). Pro libovolné slovo w G L délky alespoň n platí, že automat AI projde při akceptování slova w (alespoň) dvakrát stejným stavem. Slovo w se tedy můžeme rozdělit na tři části: w = xyz, kde y ^ e a /\ /\ /\ 5( n 3 x, y, z . (w = xyz A y ^ e A Vi > O . xi/^ G L)) Z2/ < n A Pomocí Lemmatu lze dokázat, že nějaký jazyk není regulární Necht 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\ < n a y^e • existuje alespoň jedno i G No takové, že xylz 0 L. Pak z Lemma o vkládání plyne, že L není regulární. IB102 Automaty a gramatiky, 12.10.2009 6 Příklad důkazu ne-regularity pomocí Lemmatu o vkládání L = {uď^u11 | u G {a, 6}*, m > 0} IB102 Automaty a gramatiky, 12.10.2009 7 Myhill-Nerodova věta Motivace I L = {we{a,b}* |#aH>3} IB102 Automaty a gramatiky, 12.10.2009 8 Pravá kongruence Definice 2.20. Necht S je abeceda a ^ je ekvivalence na S*. Ekvivalence ~ je pravá kongruence (zprava invariantní), pokud pro každé u,v,w G S* platí Index ekvivalence ~ je počet tříd rozkladu S*/r^. Je-li těchto tříd nekonečně mnoho, klademe index ^ roven oo. Tvrzení 2.21. Ekvivalence ^ na S* je pravá kongruence právě když pro každé u, v G S*, a G S platí u ~ v =>* ua ~ va. (Implikace =>* je triviální, implikace <= se snadno ukáže indukcí k délce zprava přiřetězeného slova w.) IB102 Automaty a gramatiky, 12.10.2009 9 Příklad S = {a, 6} ^: u rsj v «<=>* u 3 v začínají stejným symbolem (počet tříd ekvivalence 3) (počet tříd ekvivalence nekonečný) ~: u ~ v <^> u a v mají stejné předposlední písmeno IB102 Automaty a gramatiky, 12.10.2009 10 Myhill-Nerodova věta Motivace II IB102 Automaty a gramatiky, 12.10.2009 11 Prefixová ekvivalence Definice 2.25. Necht L je libovolný (ne nutně regulární) jazyk nad abecedou £. Na množině S* definujeme relaci ~L zvanou prefixová ekvivalence pro L takto: u ~r v «<=>* \/w £ S* : uw £ L <<=> vw £ L IB102 Automaty a gramatiky, 12.10.2009 12 Příklad L = {w£{a7b}* |#a(«>)>3} ~L má . . . třídy ekvivalence L = {anbn | n > 0} rsj L má . . . tříd ekvivalence IB102 Automaty a gramatiky, 12.10.2009 13 Myhill-Nerodova věta Věta 2.28. Necht L je jazyk nad S. Pak tato tvrzení jsou ekvivalentní: 1. L je rozpoznatelný konečným automatem. 2. L je sjednocením některých tříd rozkladu určeného pravou kongruenci na S* s konečným indexem. 3. Relace ~L má konečný index. Důkaz. 1^2 2^3 3^1 D IB102 Automaty a gramatiky, 12.10.2009 14 1^2 Jestliže L je rozpoznatelný konečným automatem pak L je sjednocením některých tříd rozkladu určeného pravou kongruencí na S* s konečným indexem. • pro daný L rozpoznávaný automatem A4 zkonstruujeme relaci požadovaných vlastností • M = (Q, S, ö, go, F), ö je totální • na S* definujme binární relaci ^ předpisem u ~ v <^> <$(go, u) = 5(qo, v) • ukážeme, že ^ má požadované vlastnosti IB102 Automaty a gramatiky, 12.10.2009 15 - rsj je ekvivalence (je reflexivní, symetrická, tranzitivní) - rsj má konečný index ŕr/c/y rozkladu odpovídají stavům automatu - ^ je pravá kongruence: Necht u rsj y a a G S. Pak 5(qo,ua) = 5(5(go?^)?^) 5(5(* u ~Lv pro všechna w,i;gS* (tj. R C^L) ~L každá třída ekvivalence relace R je celá obsažena v nějaké třídě ekvivalence index ekvivalence ~L je menší nebo roven indexu ekvivalence R R má konečný index => ~L má konečný index IB102 Automaty a gramatiky, 12.10.2009 17 Necht prefixová ekvivalence ~L má konečný index. Pak jazyk L je rozpoznatelný konečným automatem. Zkonstruujeme automat A4 = (Q, S, 5, go, F) přijímající L Stavy jsou třídy rozkladu S* určeného ekvivalencí ~L. (Konečnost!) F = {[v] \veL} Qo = e ô je definována pomocí reprezentantů: ô([u],a) = [i/a] Definice 5 je korektní, protože nezávisí na volbě reprezentanta. IB102 Automaty a gramatiky, 12.10.2009 18 Důkaz korektnosti, tj. L = L (M) ô ([e], v) = [v] pro každé i> G £* (ind veL(M) ^^ 5([e],v)eF ^^ IB102 Automaty a gramatiky, 12.10.2009 Použití Myhill-Nerodovy věty I L = {we{a,by I #aH > 3} Třídy ekvivalence relace ~L: Ti = {w £ {a, &}* | #a(^) T2 = {^G{a,6}*|#aH T3 = {^G{a,6}*|#aH T4 = {w e {a, by I #a(» ~L má konečný index =>> L je rozpoznatelný konečným automatem, tj. regulární IB102 Automaty a gramatiky, 12.10.2009 Použití Myhill-Nerodovy věty II n> 0} Necht i j^ j. Pak a1 ^L a*7, protože albl G L ale o?b% 0 L. Žádné ze slov a, a2, a3, a4, a5, a6,... nepadnou do stejné třídy ekvivalence relace ~L. ~L nemá konečný index =>> L není regulární (^3 =>* -il) L = {anb IB102 Automaty a gramatiky, 12.10.2009 21 Použití Myhill-Nerodovy věty III Věta 2.29. a 2.31. Minimální konečný automat akceptující jazyk L je určen jednoznačně až na isomorfismus (tj. přejmenování stavů). Počet stavů minimálního automatu rozpoznávajícího jazyk L je roven indexu prefixové ekvivalence ~L. IB102 Automaty a gramatiky, 12.10.2009 22