Regulární jazyk

Regulární jazyk ( regulární množina ) v teorii formálních jazyků  je množina slov , která rozpoznává nějaký konečný automat . Třídu regulárních množin je vhodné studovat jako celek a získané výsledky lze aplikovat na poměrně širokou škálu formálních jazyků.

Definice

Nechť  je konečná abeceda . Regulární jazyky v abecedě jsou sady slov definovaných indukcí takto:

1. Prázdná množina ( ) je regulární jazyk.
2. Sada obsahující pouze jeden prázdný řetězec ( ) je regulární jazyk.
3. Sada skládající se z jednoho jednopísmenného slova ( , kde ) je regulární jazyk.
4. Jestliže a  jsou regulární jazyky, pak jejich sjednocení ( ), zřetězení ( ) a převzetí hvězdy Kleene ( ) jsou také regulárními jazyky.
5. Neexistují žádné další regulární jazyky.

Spojení mezi automaty a běžnými jazyky

Kleeneův teorém říká, že třída regulárních jazyků je stejná jako třída jazyků rozpoznávaných konečným automatem . To znamená, že pro jakýkoli konečný automat je množina slov, kterou umožňuje, regulárním jazykem. A naopak, pro každý regulární jazyk existuje automat, který umožňuje slova z tohoto jazyka a pouze je.

Rozpoznatelná podmnožina monoidu

Tento koncept lze zobecnit na libovolný monoid. O podmnožině L monoidu M se říká , že je rozpoznatelná nad M , pokud nad M existuje konečný automat , který přijímá L. Konečný automat nad M  je automat, který bere prvky z M jako vstup . Rodina rozpoznatelných podmnožin monoidu M se obvykle označuje [1] .

Takže pokud M  je volný monoid nad abecedou , pak je rodina jednoduše rodinou regulárních jazyků .

Viz také

• Uzavřená vlastnost regulárních jazyků

Poznámky

1. ↑ Jean-Eric Pin, Mathematical Foundations of Automata Theory Archived 10. září 2014 na Wayback Machine , Kapitola IV: Rozpoznatelné a racionální množiny