Slovník pojmů (ve vývoji)

Jazyky přijímané konečnými automaty.

Alternativně (Kleene): Nejmenší třída jazyků, která obsahuje prázdný jazyk, jazyk pro každé písmeno abecedy Sigma a je uzavřená na sjednocení, zřetězení a iteraci.

\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.

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

Říkáme, že TM rozhoduje jazyk L, pokud L=L(M) a pro každé $w$ stroj nad w zastaví.

Jazyky rozhodnutelné TM nazýváme rekurzivní jazyky.