IB102 - Ukázková úloha: Myhillova-Nerodova věta Zadání U následujících jazyků rozhodněte, zda jsou regulární. Své tvrzení dokažte pomocí Myhillovy-Nerodovy věty 1. L = {w ∈ {a, b, c}∗ |#a(w) = #b(w) ∧ #(a) ≡ 1 (mod 2)} 2. L = {w ∈ {a, b, c}∗ |#a(w) = #b(w) ∨ #(a) ≡ 1 (mod 2)} Řešení V obou případech jde o neregulární jazyky: 1. Uvažme nekonečnou množinu slov M = {a2m+1 |m ∈ N}. Dokažme, že žádná dvě různá slova z M spolu neleží ve stejné třídě v rozkladu {a, b, c}∗ podle ∼L . Uvažme dvě různá slova u, v z množiny M : u = a2k+1 , v = a2l+1 , kde k = l jsou přirozená a předpokládejme pro spor, že u ∼L v. Potom dle definice ∼L pro každé w ∈ {a, b, c}∗ platí a2k+1 w ∈ L ⇐⇒ a2l+1 w ∈ L. Speciálně tedy volbou w = b2k+1 dostáváme a2k+1 b2k+1 ∈ L ⇐⇒ a2l+1 b2k+1 ∈ L, což je ovšem spor, protože a2k+1 b2k+1 ∈ L a zároveň a2l+1 b2k+1 ∈ L Sporem jsme ukázali, že každé ze slov v množině M leží v jiné třídě rozkladu Σ∗ / ∼L . Proto má prefixová ekvivalence ∼L nekonečný index a L musí být podle Myhillovy-Nerodovy věty neregulární. Poznamenejme, že stejnou práci by odvedlo lemma o vkládání pro slova a2n+1 b2n+1 a index i = 0. 2. Velice podobně, jen pro množinu M = {a2m |m ∈ N}. 1 Uvažme dva její různé prvky u, v : u = a2k , v = a2l , kde k = l jsou přirozená a předpokládejme pro spor, že u ∼L v. Potom dle definice pro každé w ∈ {a, b, c}∗ platí a2k w ∈ L ⇐⇒ a2l w ∈ L. Speciálně tedy volbou w = b2k dostáváme a2k b2k ∈ L ⇐⇒ a2l b2k ∈ L, což je ovšem spor, protože a2k b2k ∈ L a zároveň a2l b2k ∈ L. Sporem jsme ukázali, že každé ze slov v množině M leží v jiné třídě rozkladu Σ∗ / ∼L . Proto má prefixová ekvivalence ∼L nekonečný index a L musí být podle Myhillovy-Nerodovy věty neregulární. Stejnou práci by odvedlo Pumping lemma pro slovo b2n a2n a i = 0, nebo slova a2n b2n a i = 3. V obou případech zůstane po napumpování počet písmen a sudý. Navíc bude různý od počtu písmen b a tak po napumpování vypadne z jazyka L. 2