Regulární jazyk

Z Wikipedie, otevřené encyklopedie

Regulární jazyk je formální jazyk, jehož slova lze (laicky řečeno) rozpoznat tak, že při načtení každého písmene se provede změna stavu v závislosti na předchozím stavu a přečteném písmenu; pokud je výsledkem přečtení celého slova tzv. koncový stav, patří slovo do jazyka.

Formální jazyk (t.j. potenciálně nekonečnou množinu konečných posloupností symbolů z konečné množiny) můžeme nazvat regulárním jazykem, právě když:

Formálně lze množinu regulárních jazyků nad abecedou Σ definovat rekurzivně následujícím způsobem:

  • prázdný jazyk Ø je regulární.
  • jazyk obsahující jen prázdné slovo ε je regulární.
  • pro každé a ∈ Σ, jazyk { a } je regulární.
  • Pokud A a B jsou regulární jazyky, jsou A U B, AB, a A* regulární.
  • žádné další jazyky nad Σ nejsou regulární.

Všechny konečné jazyky jsou regulární. Dalším příkladem je například jazyk nad abecedou {a, b} obsahující lichý počet symbolů a.

Všechny regulární jazyky splňují nutnou podmínku, tzv. lemma o vkládání, a platí pro ně Myhillova-Nerodova věta.