Regulární výrazy\pojem{Regulární výrazy} $RV(\Sigma)$ nad konečnou neprázdnou abecedou $\Sigma=\{x_1,x_2,\ldots,x_n\}$ a jejich hodnota $L(\alpha)$ jsou definovány induktivně: Indukce: Jsou--li $\alpha$ a $\beta$ regulární výrazy s hodnotami $L(\alpha)$ and $L(\beta)$, pak |
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 |