Pumping lemma

(Česky "věta o pumpování")

  • Vlastnost regulárního jazyka

  • Platí pro každý regulární jazyk

    • (ale ne obráceně - tedy pokud platí PL, jazyk může a nemusí být regulární)

  • Lze využít k důkazu, že nějaký jazyk není regulární

  • Pro automat, který obsahuje nějakou smyčku (ze stavu do sebe samého), tedy lze opakovat/pumpovat symboly nekonečněkrát

Podstata problému

  • Předpokládejme jazyk by regulární
  • V takovém případě by byl přijímán konečným automatem s stavy
  • Nechť čte posloupnost , jednou dojde přes stavů do posledního stavu automatu - označme ho (Princip holubníku)
    • tj.
    • Neformálně - nemůže mít nekonečno stavů, takže po stavech zavedeme další poslední se smyčkou, kde se budou znaky hromadit
    • tedy nelze poté určit jejich počet
  • Mohl by nám vzniknout automat, který přijímá jiný počet než , ale to už nesplňuje zadání
  • jazyk není regulární

Formálně

  • Nechť je regulární jazyk, pak pro něj existuje konstanta taková, že pro každou větu platí:

  • Jestliže , pak lze zapsat ve tvaru tak, že:

    1. (tj. ) (smyčka nemůže být , musí mít alespoň 1 znak)
    2. (určitě se v první části věty () projde smyčkou)
    3. (smyčka se opakuje -krát)

  • Pro všechny věty , které jsou delší jak , platí, že při přijímání věty pomocí automatu se alespoň jednou projde cyklem

Příklad

  • Minimální
  • Jakékoliv věty délky 6 a více musí nutně procházet smyčkou, aby byly přijaty
    ../Attachments/pumping-lemma-pr1.svg
Pozn. pro konečný jazyk
  • U konečného jazyka je minimální rovno nejdelší přijímající větě + 1
  • Protože PL musí platit u všech regulárních jazyků, určením větší než nejdelší přijímanou větu ho tedy stále budeme splňovat

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