Slovník pojmů (ve vývoji)
definice |
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}. | |
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 | |