Slovník pojmů (ve vývoji)

Říkáme, že gramatika je v \pojem{Greibachové normální formě}, jestliže všechna pravidla mají tvar $A\rightarrow a\beta$, kde $a\in T$, $\beta\in V^*$ (řetězec neterminálů).

\pojem{Jazyk $L(G)$} generovaný gramatikou $G=(V,T,P,S)$ je množina terminálních řetězců, pro které existuje derivace ze startovního symbolu.

Mějme zásobníkový automat $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$. Pak $L(P)$, \pojem{jazyk akceptovaný koncovým stavem} je 
   \item[] $\{w |(q_0,w,Z_0)\vdash^*_P (q,\lambda,\alpha)$ pro nějaké $q\in F$ a libovolný řetězec $\alpha\in \Gamma^*, w\in \Sigma^*\}$.

 pojem{jazyk akceptovaný prázdným zásobníkem $N(P)$} definujeme
\item[]   $N(P)=\{w |(q_0,w,Z_0)\vdash^*_P (q,\lambda,\lambda)$ pro libovolné $q\in Q, w\in \Sigma^*\}$.

\item Bezkontextová gramatika  $G=(V,T,P,S)$ je \pojem{víceznačná} pokud existuje aspoň jeden řetězec $w\in T^*$ pro který můžeme najít dva různé derivační stromy, oba s kořenem $S$ dávající slovo $w$.

 \item V opačném případě nazáváme gramatiku \pojem{jednoznačnou}.

 \item Bezkontextový jazyk $L$ je \pojem{jednoznačný}, jestliže existuje jednoznačná CFG $G$ tak, že $L=L(G)$.

 \item \pojem{Bezkontextový jazyk $L$ je (podstatně) nejednoznačný}, jestliže každá CFG $G$ taková, že $L=L(G)$, je nejednoznačná. Takovému jazyku říkáme i \pojem{víceznačný}.

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

Gramatiky typu 3 nazýváme také \pojem{pravé lineární} (neterminál je vždy vpravo).

Gramatika $G$ je \pojem{levá lineání}, jestliže má pouze pravidla tvaru $A\rightarrow Bw, A\rightarrow w, A,B\in V, w\in T^*$.

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

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

\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í?