TIN

Obsah

Uzávěrové vlastnosti regulárních jazyků:

Rozhodnutelné problémy:

Closure properties of language families (<math>L_1</math> Op <math>L_2</math> where both <math>L_1</math> and <math>L_2</math> are in the language family given by the column). After Hopcroft and Ullman.
Operation		Regular	DCFL	CFL	IND	CSL	recursive	RE
Union	w \in L_1 \lor w \in L_2\} </math>	Yes	No	Yes	Yes	Yes	Yes	Yes
Intersection	w \in L_1 \land w \in L_2\}</math>	Yes	No	No	No	Yes	Yes	Yes
Complement	w \not\in L_1\}</math>	Yes	Yes	No	No	Yes	Yes	No
Concatenation	w \in L_1 \land z \in L_2\}</math>	Yes	No	Yes	Yes	Yes	Yes	Yes
Kleene star	w \in L_1 \land z \in L_1^{*}\}</math>	Yes	No	Yes	Yes	Yes	Yes	Yes
Homomorphism		Yes	No	Yes	Yes	No	No	Yes
e-free Homomorphism		Yes	No	Yes	Yes	Yes	Yes	Yes
Substitution		Yes	No	Yes	Yes	Yes	No	Yes
Inverse Homomorphism		Yes	Yes	Yes	Yes	Yes	Yes	Yes
Reverse	w \in L\} </math>	Yes	No	Yes	Yes	Yes	Yes	Yes
Intersection with a regular language	w \in L_1 \land w \in R\}, R \text{ regular}</math>	Yes	Yes	Yes	Yes	Yes	Yes	Yes

a k jazyku patřičná gramatika: context-free grammar (CFG)

Uzávěrové vlastnosti bezkontextové jazyky

k jazyk generuje kontextová gramatika context-sensitive grammar (CSG)

Někdy taky zvané Jazyky rekurzívně vyčíslitelné a jazyky rekurzívní

jazyky rekurzívně vyčíslitelné - zastaví pouze pro řětězec jazyku, který je schopen příjmout $ w \in L $
jazyky rekurzívní - pro úplný Turingův stroj (pro každý vstup se zastaví)

Mezi tyto jazyky patří například co-HP, co-MP