Slovník pojmů (ve vývoji)
A | Á | B | C | Č | D | Ď | E | É | Ě | F | G | H | CH | I | Í | J | K | L | M | N | Ň | O | Ó | P | Q | R | Ř | S | Š | T | Ť | U | Ú | Ů | V | W | X | Y | Ý | Z | Ž | VŠE
Momentální třídění: Křestní jméno vzestupně Třídit podle: Příjmení | Křestní jméno
MVMarta Vomlelová |
---|
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}. | |
Separovaná gramatikaGramatika je \pojem{separovaná}, pokud obsahuje pouze pravidla tvaru $\alpha\rightarrow \beta$, kde: | |
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. | |
Uzávěrové vlastnosti
| ||||||||||||||||||||||||||||
Zásobníkový automat (PDA)Zásobníkový automat (PDA) je $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$, kde | |