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é. |
Postův korespondenční problémInstance \pojem{Postova korespondenčního problému (PCP)} jsou dva seznamy slov nad abecedou $\Sigma$ značené $A=w_1,w_2,\ldots, w_k$ a $B=x_1,x_2,\ldots, x_k$ stejné délky $k$. Pro každé $i$, dvojice $(w_i,x_i) $ se nazývá \pojem{odpovídající} dvojice. Instance PCP \pojem{má řešení}, pokud existuje posloupnost jednoho či více přirozených čísel ${i_1}, {i_2}, \ldots, {i_m}$ tak že $w_{i_1}, w_{i_2}, \ldots, w_{i_m}=x_{i_1}, x_{i_2}, \ldots, x_{i_m} $ tj. dostaneme stejné slovo. \pojem{Postův korespondenční problém} je: Pro danou instanci PCP, rozhodněte, zda má řešení. |
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í. |