Slovník pojmů (ve vývoji)
Специальные | А | Б | В | Г | Д | Е | Ё | Ж | З | И | К | Л | М | Н | О | П | Р | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Э | Ю | Я | Все
P |
---|
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ý. | |
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)$. | |
Postova větaJazyk $L$ je rekurzivní, právě když $L$ i $\overline{L}$ (doplněk) jsou rekurzivně spočetné. | |
Příklad nerekurzivního, rekurzivně spočetného jazykaProblém zastavení TM (halting problem) je algoritmicky nerozhodnutelný. Neexistuje algoritmus, který by pro daný kód TM a daný vstup rozhodl, zda se TM zastaví. | |