Slovník pojmů (ve vývoji)

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

\pojem{Turingův stroj (TM)} je  sedmice $M=(Q,\Sigma, \Gamma, \delta,q_0,B,F)$ se složkami:
\begin{itemize}
 \item[$Q$] konečná množina \pojem{stavů}
 \item[$\Sigma$] konečná neprázdná množina \pojem{vstupních symbolů}
 \item[$\Gamma$] množina všech  \pojem{symbolů pro pásku}. Vždy $\Gamma \supseteq \Sigma$, $Q\cap \Gamma=\emptyset$.
 \item[$\delta$] \pojem{přechodová funkce}. $\delta(q,x)=(p,Y,D)$, kde:
 \begin{itemize}
 \item[$q$] $\in Q$ aktuální stav
 \item[$X$] $\in \Gamma$ aktuální symbol na pásce
  \item[$p$] nový stav,  $p\in Q$.
  \item[$Y$] $\in \Gamma$ symbol pro zapsání do aktuální buňky, přepíše aktuální obsah.
 \item[$D$] $\in \{L,R\}$ je \pojem{směr} pohybu hlavy (doleva, doprava).
 \end{itemize}
 \item[$q_0$] $\in Q$  \pojem{počáteční stav}.
  \item[$B$] $\in \Gamma \setminus \Sigma$. Blank. Symbol pro prázdné buňky, na začátku všude kromě konečného počtu buněk se vstupem.
  \item[$F$] $\subseteq Q$ množina \pojem{koncových} neboli \pojem{přijímajících} stavů.
\end{itemize}
Pozn: někdy se nerozlišuje $\Gamma$ a $\Sigma$ a neuvádí se prázdný symbol $B$, tj. pětice.

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

Gramatika je \pojem{separovaná}, pokud obsahuje pouze pravidla tvaru $\alpha\rightarrow \beta$, kde:
\begin{itemize}
 \item buď $\alpha, \beta\in V^+$ (neprázdné posloupnosti neterminálů)
 \item nebo $\alpha \in V$ a $\beta \in T\cup \{\lambda\}$.
\end{itemize}

Ří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{Dyckův jazyk} $D_n$ je definován nad abecedou $Z_n=\{a_1, a^|_1,\ldots,a_n, a^|_n\}$ následující gramatikou: $S\rightarrow \lambda| SS| a_1Sa_1^| | \ldots |a_nSa_n^| $.

Říkáme, že jazyk $L$ je \pojem{bezprefixový} pokud neexistují slova $x,y\in L$ taková, že $x$ je prefix $y$.

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^*\}$.

\pojem{Situaci} zásobníkového automatu reprezentujeme trojicí $(q,w,\gamma)$, kde
\begin{description}
 \item[$q$] je stav
 \item[$w$] je zbývající vstup a
  \item[$\gamma$] je obsah zásobníku (vrch zásobníku je vlevo).
\end{description}
Situaci značíme zkratkou \pojem{(ID)} z anglického \pojem{instantaneous description (ID)}.

Zásobníkový automat (PDA) je $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$, kde
\begin{description}
 \item[$Q$] konečná množina stavů
 \item[$\Sigma$] neprázdná konečná množina vstupních symbolů
 \item[$\Gamma$] neprázdná konečná zásobníková abeceda
 \item[$\delta$] přechodová funkce $\delta: Q\times (\Sigma\cup \{\lambda\})\times \Gamma \rightarrow P(_{FIN}(Q \times X^*)$, $(q,a,X)=(p,\gamma)$
 \begin{itemize}
  \item[] kde $p$ je nový stav a $\gamma$ je řetězec zásobníkových symbolů, který nahradí  $X$ na vrcholu zásobníku
  
 \end{itemize}
\item[$q_0\in Q$] počáteční stav
 \item[$Z_0\in \Gamma$] Počáteční zásobníkový symbol. Víc na začátku na zásobníku není.
 \item[$F$] Množina přijímajících (koncových) stavů
\end{description}

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^*$.

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

Mějme CFG $G=(V,T,P,S)$. Libovolný řetězec $\alpha\in (V\cup T)^*$ který lze odvodit $S\Rightarrow^*\alpha$ nazýváme \pojem{sentenciální forma}.

\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 gramatiku $G=(V,T,P,S)$. \pojem{Derivační strom} pro $G$ je strom, kde:
\begin{itemize}
 \item každý vnitřní uzel je ohodnocen neterminálem $V$.
 \item Každý uzel je ohodnocen prvkem $\in V \cup T \cup \{\epsilon\} $.
 \item Je--li uzel ohodnocen $\epsilon$, je jediným dítětem svého rodiče.
 \item Je--li $A$ ohodnocení vrcholu a jeho děti \alert{zleva pořadě} jsou ohodnoceny $X_1,\ldots,X_k$, pak $(A\rightarrow X_1,\ldots,X_k) \in P $ je pravidlo gramatiky.
\end{itemize}

Mějme gramatiku $G=(V,T,P,S)$.
\begin{itemize}
 \item Říkáme, že $\omega$ se \pojem{přímo přepíše} na $\gamma$ (píšeme $\omega\Rightarrow_G \gamma$ nebo $\omega\Rightarrow \gamma$) jestliže
 
 \begin{itemize}
   \item[] $\exists \alpha,\beta,\eta,\nu \in (V\cup T): \omega=\eta\alpha\nu$, $\gamma=\eta\beta\nu$ a $(\alpha\rightarrow \beta)\in P$.
 \end{itemize}
\item Říkáme, že $\omega$ se \pojem{přepíše} na $\gamma$ (píšeme $\omega\Rightarrow^* \gamma$) jestliže
\begin{itemize}
 \item[] $\exists \alpha_1,\ldots,\alpha_n\in (V\cup T)^*: \omega=\alpha_1\Rightarrow\alpha_2\Rightarrow\ldots\Rightarrow\alpha_n=\gamma$,
 \item[] tj. také $\omega\Rightarrow^*\omega$.
\end{itemize}
\item Posloupnost $\alpha_1,\ldots,\alpha_n $ nazýváme \pojem{derivací (odvozením)}.
\item Pokud $\forall i\neq j: \alpha_i\neq \alpha_j$, hovoříme o \pojem{minimálním odvození}.
\end{itemize}

Formální (generativní) gramatika je $G=(V,T,P,S)$ složena z
\begin{itemize}
 \item konečné množiny \pojem{neterminálů} (variables) $V$
 \item neprázdné konečné množiny \pojem{terminálních symbolů} (\pojem{terminálů}) $T$
 %, např. $\{0,1\} $.
 \item \pojem{počáteční symbol} $S\in V$.
 \item konečné množiny  \pojem{pravidel} (\pojem{produkcí}) $P$ reprezentující rekurzivní definici jazyka. Každé pravidlo má tvar:
 \begin{itemize}
  \item $\alpha A \beta\rightarrow \omega$, $A\in V,\alpha,\beta,\omega\in (V\cup T)^*$
  \begin{itemize}
   \item[] tj. levá strana obsahuje aspoň jeden neterminální symbol.   
  \end{itemize}
   \end{itemize}
\end{itemize}

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

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

\pojem{Dvousměrným (dvoucestným) konečným automatem} nazýváme pětici $A=(Q,\Sigma, \delta, q_0,F)$, kde
\begin{enumerate}[<+->]
 \item $Q$ je konečná množina stavů,
 \item $\Sigma$ je konečná množina vstupních symbolů
 \item  přechodové funkce $\delta$ je zobrazení z $Q \times \Sigma \rightarrow Q\times\{-1,0,1\}$ \alert{rozšířená o pohyb hlavy}
 \item $q_0\in Q$ počáteční stav
 \item a množina přijímajících stavů $F\subseteq Q$.
\end{enumerate}

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

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

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}

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.

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

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

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

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

Deterministický konečný automat (DFA) A = (Q,Σ,δ,q0 ,F) sestává z:
konečné množiny stavů, zpravidla značíme Q
konečné množiny vstupních symbolů, značíme Σ
přechodové funkce, zobrazení z Q × Σ → Q, značíme δ, která bude
reprezentovaná hranami grafu
počátečního stavu q0 ∈ Q, vede do něj šipka ’odnikud’,
a množiny koncových (přijímajících) stavů (final states) F ⊆ Q,
označených dvojitým kruhem či šipkou ’ven’.

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