Slovník pojmů (ve vývoji)
Momentální třídění: Podle data vytvoření sestupně Třídit chronologicky: Podle poslední aktualizace | Podle data vytvoření
FAviz konečné automaty (finite automata) | |
Chomského hierarchie | |
lineárně omezený automat (LBA)\pojem{Lineárně omezený automat LBA} je nedeterministický TM, kde na pásce je označen levý a pravý konec $\underline{l},\underline{r}$. Tyto symboly nelze při výpočtu přepsat a nesmí se jít nalevo od $\underline{l}$ a napravo od $\underline{r}$. Slovo $w$ \pojem{je přijímáno lineárně omezeným automatem}, pokud $q_0\underline{l}w\underline{r}\vdash^*\alpha p\beta$, $p\in F$. | |
rekurzivně spočetný jazykJazyk nazveme \pojem{rekurzivně spočetným}, pokud je přijímán nějakým Turingovým strojem $T$ (tj. $L=L(T)$). | |
Turingův stroj přijímá jazykTuringův stroj $M=(Q,\Sigma, \Gamma, \delta,q_0,B,F)$ \pojem{přijímá jazyk} $L(M)=\{w\in \Sigma^*: q_0w \vm^* \alpha p \beta, p\in F, \alpha,\beta \in \Gamma^*\} $, tj. množinu slov, po jejichž přečtení se dostane do koncového stavu. Pásku (u nás) nemusí uklízet. | |
Konfigurace Turingova stroje ID\pojem{Konfigurace Turingova stroje} (Instantaneous Description ID) je řetězec $X_1X_2\ldots X_{i-1}qX_iX_{i+1}\ldots X_n$ kde | |
Turingův stroj\pojem{Turingův stroj (TM)} je sedmice $M=(Q,\Sigma, \Gamma, \delta,q_0,B,F)$ se složkami: | |
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: | |