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 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:

• 

  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

• Obrázky, zvuky či videa k tématu Regulární jazyk na Wikimedia Commons