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í. +more * pokud A a B jsou regulární jazyky, jsou A ∪ B (sjednocení), A • B (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ž:

* je akceptovaný nějakým deterministickým konečným automatem, * je akceptovaný nějakým nedeterministickým konečným automatem, * může být popsán regulárním výrazem nebo * může být vygenerován regulární gramatikou

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:

File:Chomsky-hierarchy.svg|To, že „Regulární => bezkontextový“ a ne vždy opačně, je možné vidět na obrázku Chomského hierarchie (kterážto implikuje stromovou strukturu).

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

Regulární výraz * Regulární gramatika

Externí odkazy

Kategorie:Formální jazyky