Slovník pojmů (ve vývoji)


All categories

Page: (Previous)   1  2  3  4  (Next)
  ALL

DEFINICE

Regulární výrazy

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


rekurzivně spočetný jazyk

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


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}


PŘÍKLAD

palindrom

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


Příklad nerekurzivního, rekurzivně spočetného jazyka

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



Page: (Previous)   1  2  3  4  (Next)
  ALL