definice

Stránka: (Předchozí)   1  2  3
  VŠE

Rekurzivní jazyky

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


Sentenciální formy

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


Situace zásobníkového automatu

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


Turingův stroj

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


Turingův stroj přijímá jazyk

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.


Zásobníkový automat (PDA)

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}



Stránka: (Předchozí)   1  2  3
  VŠE