Regulární jazyk

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Regulární jazyky jsou jakési nejjednodušší formální jazyky. Regulární jazyky nad abecedou Σ lze zavést následujícím způsobem:

  • prázdný jazyk Ø je regulární.
  • pro každé a z abecedy, jazyk { a } je regulární.
  • pokud A a B jsou regulární jazyky, jsou AB (sjednocení), AB (konkatenace), a A* (iterace) také regulární.
  • žádné další jazyky regulární nejsou.


O regulárních jazycích lze dokázat řadu tvrzení. Např. formální jazyk je regulární, právě když:


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 jsou bezkontextové, ale ne všechny bezkontextové jazyky jsou regulární. Tomuto je možno snadno nahlédnout díky Chomského Hierarchii na obrázku :

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

Odkazy[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]