\pojem{Regulární výrazy} $RV(\Sigma)$ nad konečnou neprázdnou abecedou $\Sigma=\{x_1,x_2,\ldots,x_n\}$ a jejich hodnota $L(\alpha)$ jsou definovány induktivně:
Základ:
\begin{enumerate}
 \item Konstanty $\lambda$ a $\emptyset$ jsou regulární výrazy s hodnotami $L(\lambda)=\{\lambda\}$ a $L(\emptyset)=\emptyset$ (někdy značeno $\left[\lambda\right]$, $\left[\emptyset\right]$).
 \item Je--li $a\in \Sigma$, je ${\bf a}$ regulární výraz s hodnotou $L({\bf a})=\{a\}$.
 \item řecká písmena z počátku abecedy $\alpha,\beta$ budeme používat jako proměnné reprezentující libovolný jazyk $\alpha\in RV(\Sigma)$.
\end{enumerate}

Indukce: Jsou--li $\alpha$ a $\beta$ regulární výrazy s hodnotami $L(\alpha)$ and $L(\beta)$, pak
\begin{enumerate}
 \item $\alpha+\beta$ je RE s hodnotou $L(\alpha+\beta)=L(\alpha)\cup L(\beta) $.
 \item $\alpha\beta$ je RE s hodnotou $L(\alpha\beta)=L(\alpha)L(\beta)$. (Tečce používané u řetězců se vyhýbáme, aby se nepletla s jiným významem v  UNIX grep příkazu.)
 \item uzávěr $\alpha^*$ je RE s hodnotou $L(\alpha^*)=(L(\alpha))^*$.
 \item $(\alpha)$ je RE se stejnou hodnotou jako  $\alpha$, i.e. $L((\alpha))=L(\alpha)$.
\end{enumerate}
Každý regulární výraz dostaneme indukcí výše, tj. třída $RE(\Sigma)$ je nejmenší třída uzavřená na uvedené operace.

viz konečné automaty (finite automata)

O bezkontextové gramatice $G=(V,T,P,S)$ bez zbytečných symbolů kde jsou všechna pravidla v jednom ze dvou tvarů
\begin{itemize}
 \item $A\rightarrow BC$, $A,B,C\in V$,
 \item $A\rightarrow a$, $A\in V$, $a\in T$,
\end{itemize}
říkáme, že je v  \pojem{Chomského normálním tvaru (ChNF)}.

Problém zastavení TM (halting problem) je algoritmicky nerozhodnutelný.

Neexistuje algoritmus, který by pro daný kód TM a daný vstup rozhodl, zda se TM zastaví.

\pojem{Lineárně omezený automat LBA} je nedeterministický TM, kde na pásce je označen levý a pravý konec $\underline{l},\underline{r}$. Tyto symboly nelze při výpočtu přepsat a nesmí se jít nalevo od $\underline{l}$ a napravo od $\underline{r}$.

Slovo $w$ \pojem{je přijímáno lineárně omezeným automatem}, pokud $q_0\underline{l}w\underline{r}\vdash^*\alpha p\beta$, $p\in F$.

Jazyk nazveme \pojem{rekurzivně spočetným}, pokud je přijímán nějakým Turingovým strojem $T$ (tj. $L=L(T)$).

Turingův stroj $M=(Q,\Sigma, \Gamma, \delta,q_0,B,F)$ \pojem{přijímá jazyk} $L(M)=\{w\in \Sigma^*: q_0w \vm^* \alpha p \beta, p\in F, \alpha,\beta \in \Gamma^*\} $, tj. množinu slov, po jejichž přečtení se dostane do koncového stavu. Pásku (u nás) nemusí uklízet.

\pojem{Konfigurace Turingova stroje} (Instantaneous Description ID) je řetězec $X_1X_2\ldots X_{i-1}qX_iX_{i+1}\ldots X_n$ kde
\begin{itemize}
 \item $q$ je stav Turingova stroje
 \item čtecí hlava je vlevo od  $i$--tého symbolu
 \item $X_1\ldots X_n$ je část pásky mezi nejlevějším a nejpravějším symbolem různým od prázdného ($B$). S výjimkou v případě, že je hlava na kraji -- pak na tom kraji vkládáme jeden $B$ navíc.
\end{itemize}