Slovník pojmů (ve vývoji)


All categories

Page: (Previous)   1  2  3  4
  ALL

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)



Page: (Previous)   1  2  3  4
  ALL