Regulární jazyk

nejjednodušší formální jazyky

Regulární jazyky jsou nejjednodušší formální jazyky v rámci Chomského hierarchie. 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.

Související články

editovat

Externí odkazy

editovat