Slovník pojmů (ve vývoji)

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}

 \item Ze vstupního DFA $A$ eliminujeme stavy nedosažitelné z počátečního stavu.
\item Najdeme rozklad zbylých stavů na třídy ekvivalence.
\item Konstruujeme DFA $B$ na třídách ekvivalence jakožto stavech. Přechodovou funkci $B$ označíme $\gamma$, mějme $S\in Q_B$. Pro libovolné $q\in S$, označíme $T$ třídu ekvivalence $\delta(q,a)$ a definujeme $\gamma(S,a)=T$. Tato třída musí být stejná pro všechna $a \in S$.
\item Počáteční stav $B$ je třída obsahující počáteční stav $A$.
\item Množina přijímajících stavů $B$ jsou bloky odpovídající přijímajícím stavům $A$.

\pojem{Palindrom} je řetězec $w$ stejný při čtení zepředu i zedadu, tj. $w=w^R$.

Jazyk palindromů není regulární, je bezkontextový.

\pojem{Podmnožinová konstrukce} začíná s NFA $N=(Q_N,\Sigma,\delta_N,q_0,F_N)$. Cílem je popis deterministického DFA $D=(Q_D,\Sigma,\delta_D,\{q_0\},F_D)$, pro který $L(N)=L(D)$.
\begin{itemize}
\item $Q_D$ je množina podmnožin $Q_N$, $Q_D={\cal P}(Q_N)$ (potenční množina). {\footnotesize Nedosažitelné stavy můžeme vynechat.}
\item $F_D=\{S: S\in {\cal P}(Q_N)\ \&\ S \cup F_N \neq \emptyset\}$, tedy $S$ obsahuje alespoň jeden přijímající stav $N$.
\item Pro každé $S\subseteq Q_N$ a každý vstupní symbol $a\in \Sigma$,
$\delta_D(S,a)=\bigcup_{p \in S}\delta_N(p,a)\hbox{.}$
\end{itemize}

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

Instance \pojem{Postova korespondenčního problému (PCP)} jsou dva seznamy slov nad abecedou $\Sigma$ značené $A=w_1,w_2,\ldots, w_k$ a $B=x_1,x_2,\ldots, x_k$ stejné délky $k$. Pro každé $i$, dvojice $(w_i,x_i) $ se nazývá \pojem{odpovídající} dvojice.

Instance PCP \pojem{má řešení}, pokud existuje posloupnost jednoho či více přirozených čísel ${i_1}, {i_2}, \ldots, {i_m}$ tak že $w_{i_1}, w_{i_2}, \ldots, w_{i_m}=x_{i_1}, x_{i_2}, \ldots, x_{i_m} $ tj. dostaneme stejné slovo.
V tom případě říkáme, že posloupnost ${i_1}, {i_2}, \ldots, {i_m}$  \pojem{je řešení}.

\pojem{Postův korespondenční problém} je: Pro danou instanci PCP, rozhodněte, zda má řešení.

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

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.