Slovník pojmů (ve vývoji)
Momentální třídění: Podle data vytvoření vzestupně Třídit chronologicky: Podle poslední aktualizace | Podle data vytvoření
Podmnožinová konstrukce (FA z NFA)\pojem{Podmnožinová konstrukce} začíná s NFA $N=(Q_N,\Sigma,\delta_N,q_0,F_N)$. Cílem je popis deterministického DFA $D=(Q_D,\Sigma,\delta_D,\{q_0\},F_D)$, pro který $L(N)=L(D)$. | |
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 | |
Regulární výrazy\pojem{Regulární výrazy} $RV(\Sigma)$ nad konečnou neprázdnou abecedou $\Sigma=\{x_1,x_2,\ldots,x_n\}$ a jejich hodnota $L(\alpha)$ jsou definovány induktivně: Indukce: Jsou--li $\alpha$ a $\beta$ regulární výrazy s hodnotami $L(\alpha)$ and $L(\beta)$, pak | |
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. | |