bezprefixové jazykyŘíkáme, že jazyk $L$ je \pojem{bezprefixový} pokud neexistují slova $x,y\in L$ taková, že $x$ je prefix $y$. |
Chomského hierarchie |
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ů |
Derivace $\Rightarrow^*$Mějme gramatiku $G=(V,T,P,S)$. |
deterministický konečný automatDeterministický konečný automat (DFA) A = (Q,Σ,δ,q0 ,F) sestává z: |
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 |
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^| $. |
Gramatika = Formální (generativní) gramatikaFormální (generativní) gramatika je $G=(V,T,P,S)$ složena z |
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ů). |
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 |