Regulární jazyk
Z Wikipedie, otevřené encyklopedie
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.
