⟸ Go Back ⟸

Exercise 1 (Homework 5).

(Turing machines)

Turing machines for simple languages

Describe explicitly a (deterministic) Turing machine deciding the following languages:

1. \{a^nb^nc^n \mid n\in \mathbb N\}
2. \{x\# y \mid x,y\in \{0,1\}^* \land \mathrm{value}_2(x)=\mathrm{value}_2(y)+1\}
3. \{ww \mid w\in \{0,1\}^*\}
4. \{a^{2^n} \mid n\in \mathbb N\}
5. \{a^{n^2} \mid n\in \mathbb N\}
6. \{a^{2^n}b^n \mid n\in \mathbb N\}
7. \{w\in \{a,b\}^* \mid |w|_a=|w|_b^2\}

Tip

For some languages above it might be simpler to describe a Turing machine with two or more tapes instead of a 1-tape Turing machine.