Sentenciální formyMě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í gramatikyGramatiky 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 |
Situace zásobníkového automatu\pojem{Situaci} zásobníkového automatu reprezentujeme trojicí $(q,w,\gamma)$, kde |
Jazyk přijímaný PDA koncovým stavem, prázdným zásobníkemMě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 pojem{jazyk akceptovaný prázdným zásobníkem $N(P)$} definujeme |
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 CFGO bezkontextové gramatice $G=(V,T,P,S)$ bez zbytečných symbolů kde jsou všechna pravidla v jednom ze dvou tvarů |