Slovník pojmů (ve vývoji)
Všechny kategorie |
DEFINICE |
---|
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)$). | |
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. | |
Sentenciální formyMějme CFG $G=(V,T,P,S)$. Libovolný řetězec $\alpha\in (V\cup T)^*$ který lze odvodit $S\Rightarrow^*\alpha$ nazýváme \pojem{sentenciální forma}. | |
Situace zásobníkového automatu\pojem{Situaci} zásobníkového automatu reprezentujeme trojicí $(q,w,\gamma)$, kde | |
Turingův stroj\pojem{Turingův stroj (TM)} je sedmice $M=(Q,\Sigma, \Gamma, \delta,q_0,B,F)$ se složkami: | |
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. | |
Zásobníkový automat (PDA)Zásobníkový automat (PDA) je $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$, kde | |
PŘÍKLAD |
---|
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ý. | |
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í. | |