Regulární jazyk

Regulární jazyk je formální jazyk, jehož slova lze (laicky řečeno) rozpoznat tak, že při načtení každého písmene se provede změna stavu v závislosti na předchozím stavu a přečteném písmenu; pokud je výsledkem přečtení celého slova tzv. koncový stav, patří slovo do jazyka.

Formální jazyk (t.j. potenciálně nekonečnou množinu konečných posloupností symbolů z konečné množiny) můžeme nazvat regulárním jazykem, 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

Formálně lze množinu regulárních jazyků nad abecedou Σ definovat rekurzivně následujícím způsobem:

• prázdný jazyk Ø je regulární.
• jazyk obsahující jen prázdné slovo ε je regulární.
• pro každé a ∈ Σ, jazyk { a } je regulární.
• Pokud A a B jsou regulární jazyky, jsou A U B, A • B, a A* regulární.
• žádné další jazyky nad Σ nejsou regulární.

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 splňují nutnou podmínku, tzv. lemma o vkládání, a platí pro ně Myhillova-Nerodova věta.

[editovat] Odkazy

[editovat] Související články

• Regulární výraz