\pojem{Mealyho (sekvenčním) strojem} nazýváme šestici $A=(Q,\Sigma, Y,\delta, \lambda_M,q_0)$ resp. pětici $A=(Q,\Sigma, Y,\delta, \lambda_M) $, kde
\begin{itemize}
 \item[] $Q$ je konečná neprázdná množina stavů
 \item[] $\Sigma$ je konečná neprázdná množina symbolů (vstupní abeceda)
 \item[] $Y$ je konečná neprázdná množina symbolů (výstupní abeceda)
 \item[] $\delta$ je zobrazení $Q\times \Sigma \rightarrow Q$ (přechodová funkce)
 \item[] $\lambda_M$ je zobrazení $Q\rightarrow Y$ (\pojem{výstupní funkce})
 \item[] $q_0\in Q$ (počáteční stav)
\end{itemize}

Mějme PCP, tj. seznamy $A=w_1,w_2,\ldots, w_k$ a $B=x_1,x_2,\ldots, x_k$. Hledáme seznam 0 nebo více přirozených čísel  ${i_1}, {i_2}, \ldots, {i_m}$ tak že ${\bf w_1,}w_{i_1}, w_{i_2}, \ldots, w_{i_m}={\bf x_1,}x_{i_1}, x_{i_2}, \ldots, x_{i_m} $. V tom případě říkáme, že PCP \pojem{má iniciální řešení}.

\pojem{Modifikovaný Postův korespondenční problém}: má PCP iniciální řešení?

Gramatika je \pojem{monotónní (nevypouštějící)}, jestliže pro každé pravidlo $(\alpha\rightarrow \beta)\in P$ platí $|\alpha|\leq|\beta|$.  Monotónní gramatiky slovo v průběhu generování nezkracují.

\pojem{Mooreovým (sekvenčním) strojem} nazýváme šestici $A=(Q,\Sigma, Y,\delta, \mu,q_0)$ resp. pětici $A=(Q,\Sigma, Y,\delta, \mu) $, kde
\begin{itemize}
 \item[] $Q$ je konečná neprázdná množina stavů
 \item[] $\Sigma$ je konečná neprázdná množina symbolů (vstupní abeceda)
 \item[] $Y$ je konečná neprázdná množina symbolů (\pojem{výstupní abeceda})
 \item[] $\delta$ je zobrazení $Q\times \Sigma \rightarrow Q$ (přechodová funkce)
 \item[] $\mu$ je zobrazení $Q\rightarrow Y$ (\pojem{značkovací funkce})
 \item[] $q_0\in Q$ (počáteční stav)
\end{itemize}

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}