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í. |
Mooreův stroj\pojem{Mooreovým (sekvenčním) strojem} nazýváme šestici $A=(Q,\Sigma, Y,\delta, \mu,q_0)$ resp. pětici $A=(Q,\Sigma, Y,\delta, \mu) $, kde |
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. |
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í. |
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. |