Dvousměrné (dvoucestné) konečné automaty\pojem{Dvousměrným (dvoucestným) konečným automatem} nazýváme pětici $A=(Q,\Sigma, \delta, q_0,F)$, kde |
Mooreův stroj\pojem{Mooreovým (sekvenčním) strojem} nazýváme šestici $A=(Q,\Sigma, Y,\delta, \mu,q_0)$ resp. pětici $A=(Q,\Sigma, Y,\delta, \mu) $, kde |
Mealyho stroj\pojem{Mealyho (sekvenčním) strojem} nazýváme šestici $A=(Q,\Sigma, Y,\delta, \lambda_M,q_0)$ resp. pětici $A=(Q,\Sigma, Y,\delta, \lambda_M) $, kde |
palindrom\pojem{Palindrom} je řetězec $w$ stejný při čtení zepředu i zedadu, tj. $w=w^R$.
Jazyk palindromů není regulární, je bezkontextový. |
Gramatika = Formální (generativní) gramatikaFormální (generativní) gramatika je $G=(V,T,P,S)$ složena z |
Derivace $\Rightarrow^*$Mějme gramatiku $G=(V,T,P,S)$. |
Derivační stromMějme gramatiku $G=(V,T,P,S)$. \pojem{Derivační strom} pro $G$ je strom, kde: |
Jazyk generovaný gramatikou $G$\pojem{Jazyk $L(G)$} generovaný gramatikou $G=(V,T,P,S)$ je množina terminálních řetězců, pro které existuje derivace ze startovního symbolu. |
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ý}. |