Regulární jazyk

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.

Odkazy

Související články

Externí odkazy

Média použitá na této stránce

Chomsky-hierarchy.svg
Autor: J. Finkelstein, Licence: CC BY-SA 3.0
A graphical representation of the sets of languages included in the w:Chomsky hierarchy.