Thursday, 7 November 2024, 4:16 AM
Site: Moodle UK pro výuku 1
Course: Automaty a gramatiky (Automaty a gramatiky)
Glossary: Slovník pojmů (ve vývoji)
S

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

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}

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