Word (formální jazyk)

Slovo formálního jazyka (též řetěz , řádek ) je libovolná posloupnost znaků z dané abecedy . Počet znaků ve slově se nazývá jeho délka a značí se . Jedno slovo délky 0, ( prázdné slovo ), které neobsahuje žádné znaky (označené , nebo ), může být povoleno. $\alpha$ $|\alpha |$ $E$ $\varepsilon$ $\lambda$

Množinu všech slov délky v abecedě značíme , v konečné abecedě je počet takových slov přesně roven velikosti abecedy na mocninu ( ). Množina všech slov v abecedě (libovolné délky) je označena ( Kleenova hvězda ), tedy: $n$ $A$ $A^{n}$ $n$ $|A^{n}|=|A|^{n}$ $A$ $A^{*}$

A^{*}=\bigcup _{n=0}^{+\infty }A^{n}.

Na slovech v dané abecedě je definována operace zřetězení , tedy postupného slepování slov. Množina všech slov v abecedě s operací zřetězení tvoří monoid ( volný monoid ). Množina všech neprázdných slov v abecedě s operací zřetězení tvoří pologrupu . $A$ $A$ $A$

Formální jazyky a formální gramatiky
Obecné pojmy	Chomského hierarchie Abeceda Slovo
Typ 0	Neomezená gramatika Turingův stroj výčtový jazyk Řešitelný jazyk
Typ 1	Kontextově citlivá gramatika Kontextový jazyk Lineárně ohraničený automat
Typ 2	Bezkontextová gramatika Nejednoznačná gramatika Bezkontextový jazyk Zásobníkový automat ( deterministický ) Růstové lemma Ogdenovo lemma Cookova věta
Typ 3	Pravidelná gramatika regulární jazyk Regulární výraz Stavový stroj ( deterministický , nedeterministický ) Minimalizace DFA Stanovení NFA Myhillova-Nerodova věta
rozebrat	LL analyzátor LR analyzátor Metoda rekurzivního sestupu Kok-Younger-Kasami algoritmus