Slovník pojmů (ve vývoji)

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

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

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}

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

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

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}

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

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