Momentální třídění: Podle data vytvoření vzestupně Třídit chronologicky: Podle poslední aktualizace | Podle data vytvoření změnit na sestupně

Stránka: (Předchozí)   1  2  3  4  (Další)
  VŠE

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


Jednoznačnost a víceznačnost CFG

\item Bezkontextová gramatika  $G=(V,T,P,S)$ je \pojem{víceznačná} pokud existuje aspoň jeden řetězec $w\in T^*$ pro který můžeme najít dva různé derivační stromy, oba s kořenem $S$ dávající slovo $w$.

 \item V opačném případě nazáváme gramatiku \pojem{jednoznačnou}.

 \item Bezkontextový jazyk $L$ je \pojem{jednoznačný}, jestliže existuje jednoznačná CFG $G$ tak, že $L=L(G)$.

 \item \pojem{Bezkontextový jazyk $L$ je (podstatně) nejednoznačný}, jestliže každá CFG $G$ taková, že $L=L(G)$, je nejednoznačná. Takovému jazyku říkáme i \pojem{víceznačný}.


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


Chomského normální tvar CFG

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



Stránka: (Předchozí)   1  2  3  4  (Další)
  VŠE