Slovník pojmů (ve vývoji)

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

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

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