Saturday, 21 May 2022, 8:17 PM
Site: Moodle UK pro výuku 1
Course: Automaty a gramatiky (Automaty a gramatiky)
Glossary: Slovník pojmů (ve vývoji)

Levé (a pravé) lineání gramatiky

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

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}

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

Jazyk přijímaný PDA koncovým stavem, prázdným zásobníkem

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

bezprefixové jazyky

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

Dyckův jazyk

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

Greibachové normální forma CFG

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

Separovaná gramatika

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}

monotónní (nevypouštějící) gramatika

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

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.