Exercici 1 (Tasca 5).
(Turing machines)
Màquines de Turing per llenguatges senzills
Descriviu màquines de Turing deterministes que decideixin els llenguatges següents:
- \{a^nb^nc^n \mid n\in \mathbb N\}
- \{x\# y \mid x,y\in \{0,1\}^* \land \mathrm{value}_2(x)=\mathrm{value}_2(y)+1\}
- \{ww \mid w\in \{0,1\}^*\}
- \{a^{2^n} \mid n\in \mathbb N\}
- \{a^{n^2} \mid n\in \mathbb N\}
- \{a^{2^n}b^n \mid n\in \mathbb N\}
- \{w\in \{a,b\}^* \mid |w|_a=|w|_b^2\}
Consell
Per alguns dels llenguatges definits més amunt, podria ser més senzill descriure una màquina de Turing amb dues o més cintes en lloc d’una màquina d’una sola cinta.