Thursday, 11 August 2022, 4:49 PM
Site: Moodle UK pro výuku 1
Course: Automaty a gramatiky (Automaty a gramatiky)
Glossary: Slovník pojmů (ve vývoji)
VĚTA

Myhill--Nerodova věta

Nechť $L$ je jazyk nad konečnou abecedou $\Sigma$. Potom následující tvrzení jsou ekvivalentní:
\begin{itemize}
 \item[a)] $L$ je rozpoznatelný konečným automatem,
 \item[b)] existuje pravá kongruence $\sim$ konečného indexu nad $\sigma^*$ tak, že $L$ je sjednocením jistých tříd rozkladu $\Sigma^*/\sim$.
\end{itemize}

Postova věta

Jazyk $L$ je rekurzivní, právě když $L$ i $\overline{L}$ (doplněk) jsou rekurzivně spočetné.

Uzávěrové vlastnosti

jazyk regulární bezkontext.

deterministické

bezkontextové

sjednocení ANO ANO NE
průnik ANO NE NE
∪ s RL ANO ANO ANO
doplněk ANO NE ANO
homomorfismus ANO ANO NE
inverzní hom. ANO ANO ANO
ZKRATKY

FA

viz konečné automaty (finite automata)