Description
1. [30 Points] Classify the following languages into one of the three categories a) regular,
b) context-free but not regular, and c) not context-free. Prove your answer.
(a) L1 = {a
i
b
j
c
k
| k = i × j and 0 < i < 10 < j}
(b) L2 = {xyz | x, y, z ∈ {a, b}
⋆ and na(x) = nb(z)}
(c) L3 = {wuwR | w, u ∈ {a, b}
⋆ and |w| = |u|}
Note that in order to show that a language is context-free but not regular, you need
to prove both that it is context-free and also that it is not regular.
2. [10 Points] Give a Turing machine for L = {a}·{a, b}
+ that does not halt on rejection.
3. [20 Points] Give a Turing machine for each of the following languages:
(a) L1 = {a
n
b
mc
k
| m ≥ n, k ≥ 1}.
(b) L2 = {xy | x ∈ {a, b}
+, y ∈ {c}
+ and na(x) = nc(y)}.
4. [20 Points] Draw transition diagrams for Turing machines that compute the following
functions. In each case, give a brief description in English of your solution strategy.
(a) f(1n
) = 12n
(b) f(1n
) = 1n
2
