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í
deterministický konečný automatDeterministický konečný automat (DFA) A = (Q,Σ,δ,q0 ,F) sestává z: | ||
Lineárně omezené automaty\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$. | |
Modifikovaný Postův korespondenční probémMějme PCP, tj. seznamy $A=w_1,w_2,\ldots, w_k$ a $B=x_1,x_2,\ldots, x_k$. Hledáme seznam 0 nebo více přirozených čísel ${i_1}, {i_2}, \ldots, {i_m}$ tak že ${\bf w_1,}w_{i_1}, w_{i_2}, \ldots, w_{i_m}={\bf x_1,}x_{i_1}, x_{i_2}, \ldots, x_{i_m} $. V tom případě říkáme, že PCP \pojem{má iniciální řešení}. \pojem{Modifikovaný Postův korespondenční problém}: má PCP iniciální řešení? | |
Postova větaJazyk $L$ je rekurzivní, právě když $L$ i $\overline{L}$ (doplněk) jsou rekurzivně spočetné. | |
Rekurzivní jazykyŘíkáme, že TM rozhoduje jazyk L, pokud L=L(M) a pro každé $w$ stroj nad w zastaví. Jazyky rozhodnutelné TM nazýváme rekurzivní jazyky. | |
regulární jazykyJazyky přijímané konečnými automaty.
Alternativně (Kleene): Nejmenší třída jazyků, která obsahuje prázdný jazyk, jazyk pro každé písmeno abecedy Sigma a je uzavřená na sjednocení, zřetězení a iteraci. | |
Myhill--Nerodova větaNechť $L$ je jazyk nad konečnou abecedou $\Sigma$. Potom následující tvrzení jsou ekvivalentní: | |
Nalezení reduktu deterministického konečného automatu \item Ze vstupního DFA $A$ eliminujeme stavy nedosažitelné z počátečního stavu. | |
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)$. | |