Použití pumping lemma

Použití pumping lemma k důkazu, že jazyk není regulární

  • Důkaz, že jazyk není regulární

    • Předpokládejme, že je regulární
    • Pak pomocí pumping lemma musí platit, že existuje , že lze zapsat ve tvaru

  • Věta je zřejmě delší než musí splňovat PL

  • K důkazu zkusíme všechny možné rozdělení na

  • Musíme pak ukázat, že každé z nich porušuje alespoň jednu z podmínek PL

Postup

  1. Vyberu jednu vhodnou větu , jejíž délka
    • protože má symbolů a symbolů má symbolů, tedy je delší než
  2. Dokázat, že nelze rozepsat jako
    • může dosahovat pouze do první jedničky (vyjma ní) - neprázdná posloupnost nul
    • - obsahuje všechny jedničky
  3. Vyzkoušet, jestli pro všechny moje způsoby v kroku 2 platí třetí podmínka
    • Např. pro
      • je ale menší než , nerovná se
      • tedy tato věta nepatří do

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25