1. Adjunk olyan Turing-gépet, ami az input szó elé és mögé betesz egy-egy markert. 2. Gondoljuk meg, hogy hogyan lehet olyan szubrutinszerűen működő Turing-gépet csinálni, ami (a) beszúr egy megjelölt helyre egy megadott szimbólumot (b) töröl egy adott helyről , úgy hogy a szalagon a törlés helyétől jobbra levő szimbólumokat is visszahúzza. 3. Adjunk Turing-gépet, ami az $L=\{a^nb^nc^n\;\vert\;n\geq 1\;\}$ nyelvet ismeri fel! Olyat adjunk ami lineárisan korlátolt! 4. Milyen nyelvet generál az alábbi nyelvtan? $S\ensuremath{\rightarrow} XYBBAZ$, $Y\ensuremath{\rightarrow} AYB\;\vert\;\epsilon$, $AB\ensuremath{\rightarrow} BaA$, $aA\ensuremath{\rightarrow} Aa$, $aB\ensuremath{\rightarrow} Ba$, $XB\ensuremath{\rightarrow} X\;\vert\;\epsilon$, $AZ\ensuremath{\rightarrow} Z\;\vert\;\epsilon$. 5. Lássuk be, hogy a CS nyelvtanokra adott két definíció ekvivalens, azaz ha adott egy nyelvtan, ami nem-csökkentő szabályokból áll, (plusz esetleg az $S\ensuremath{\rightarrow}\epsilon$, de akkor az S nem áll szabály jobb-oldalán) akkor van egy ugyanezt a nyelvet generáló olyan nyelvtan, ami csupa ${\gamma}_1A{\gamma}_2\ensuremath{\rightarrow} {\gamma}_1z{\gamma}_2$ alakú szabályból áll, ahol $z\not=\epsilon$ (plusz esetleg az $S\ensuremath{\rightarrow}\epsilon$, de akkor az S nem áll szabály jobb-oldalán) és megfordítva.