Slovník pojmů (ve vývoji)
Momentální třídění: Podle poslední aktualizace vzestupně Třídit chronologicky: Podle poslední aktualizace | Podle data vytvoření
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ý}. | |