Slovník pojmů (ve vývoji)

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}

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

viz konečné automaty (finite automata)