Regulární jazyky
Regulární jazyk je typ formálního jazyka v Chomského hierarchii. Je generovaný formální regulární gramatikou (gramatika konečněstavová) a rozpoznatelný tzv. konečným automatem.
Formální gramatika v informatice označuje strukturu, která popisuje formální jazyk.
Formální jazyk je libovolná množina konečných řetězců nad určitou abecedou.
Chomského hierarchie je hierarchie tříd formálních gramatik generujících formální jazyky. Skládá se ze 4 gramatik (poslední a nejjednodušší je právě ta, co generuje regulární jazyky).
 |
|---|
| obr. 1: Chomského hierarchie |
Regulární výrazy
Pomocí symbolů abecedy Σ, závorek a operátorů + (sjednocení), · (zřetězení) a * (uzávěr) můžeme definovat složitější jazyky jako kombinace jednodušších.
| Regulární výraz | Jazyk |
|---|---|
| a | {a} |
| a + b + c | {a, b, c} |
| (a + (b · c))* | {λ, a, bc, aa, abc, bca, bcbc, aaa, aabc, . . .} |
Z toho vyplývá, že regulární výraz je posloupnost znaků a několika speciálních symbolů, jejichž vyhodnocením je (formální) jazyk.
Vlastnosti regulárních jazyků
Jazyk L(r) reprezentovaný regulárním výrazem r se nazývá regulární jazyk. Je definován následujícími pravidly:
- regulární výraz Ø označuje prázdný jazyk
- regulární výraz λ označuje jazyk {λ}
- pro každé a ϵ Σ označuje regulární výraz a jednoprvkový jazyk {a}
- pokud A a B jsou regulární jazyky, jsou A ∪ B (sjednocení), A ∙ B (konkatenace), a A* (iterace) také regulární.
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
- může být vygenerován regulární gramatikou
Všechny konečné jazyky jsou regulární a všechny regulární jazyky jsou bezkontextové.
Citace
- Wikipedie: Otevřená encyklopedie: Chomského hierarchie [online]. c2022 [citováno 18. 01. 2023]. Dostupný z WWW: https://cs.wikipedia.org/w/index.php?title=Chomsk%C3%A9ho_hierarchie&oldid=21841492
- PETKEVIČ, Vladimír. Regulární gramatika. CzechEncy - Nový encyklopedický slovník češtiny [online]. Brno, c2012-2020 [cit. 2023-01-18]. Dostupné z: https://www.czechency.org/slovnik/REGUL%C3%81RN%C3%8D%20GRAMATIKA