Slovník pojmů (ve vývoji)
Momentální třídění: Podle poslední aktualizace sestupně Třídit chronologicky: Podle poslední aktualizace | Podle data vytvoření
monotónní (nevypouštějící) gramatikaGramatika je \pojem{monotónní (nevypouštějící)}, jestliže pro každé pravidlo $(\alpha\rightarrow \beta)\in P$ platí $|\alpha|\leq|\beta|$. Monotónní gramatiky slovo v průběhu generování nezkracují. | |
Separovaná gramatikaGramatika je \pojem{separovaná}, pokud obsahuje pouze pravidla tvaru $\alpha\rightarrow \beta$, kde: | |
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ů). | |
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^| $. | |
bezprefixové jazykyŘíkáme, že jazyk $L$ je \pojem{bezprefixový} pokud neexistují slova $x,y\in L$ taková, že $x$ je prefix $y$. | |
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 | |
Situace zásobníkového automatu\pojem{Situaci} zásobníkového automatu reprezentujeme trojicí $(q,w,\gamma)$, kde | |
Zásobníkový automat (PDA)Zásobníkový automat (PDA) je $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$, kde | |
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^*$. | |