Problem 1 (8 points) Pumping Lemma.

In this problem, you will show that the language

L = {w ∈ {a,b,c}*  | w has less a’s than b’s and less b’s than c’s}

is not context-free.

(a) Use the Pumping Lemma to show that the language {aibj ck   |  1 ≤ i < j < k} is not context-free.

(b)  Use closure properties of CFLs to conclude that L is not context-free.  (Don’t give a direct proof.)

Problem 2 (9 points) Context-free or not context-free?

For each of the following languages over the alphabet {a,b} state whether it is context-free or not. Prove your statement or say where a proof was given in class.

(a)  L1  = {w ∈ {a,b}∗ | w = wR }

(b)  L2  = {w ∈ {a,b}∗ | w has the same number of a’s and b’s}

(c)  L3  = L1 ∩ L2

Problem 3 (8 points) Deciders vs. Recognizers.

Four (standard one-way) Turing machines M1 , M2 , M3 , M4  are given below. For each machine Mi :

–  Give a precise description of the language L = L(Mi ) accepted by the machine.

–  State whether Mi  is a decider or only a recognizer and explain your answer.

Each machine has the form (Q,Σ , Γ,δ,s,qaccept ,qreject ) with Σ = {0, 1}, Γ = {0, 1, ⊔}, and Q = {s,q,qaccept ,qreject }. Transitions δ are specified in each case.

(a) M1  has transitions (b) M2  has transitions

s    1       s              1    R                                     s    1       s           1    L

s     0         s           0    R                                     s     0         q             0    R

s    ⊔   q           ⊔  L                                     s    ⊔    qreject        1    R

q     1       qaccept       1    R                                        q    1       q            1     R

q   0       q           0     R                                     q   0       q           0     R

q ⊔ qreject ⊔ R                                     q ⊔ qaccept ⊔ L

(c) M3  has transitions (d) M4  has transitions

s    1         q             0    R                                     s    1       q           1    R

s    0       s           ⊔  L                                     s    0       q           0     R

s ⊔ qreject ⊔ R                                   s ⊔ qreject ⊔ R

q    1       s              1    L                                     q     1       qaccept      1    R

q    0       qaccept       0     L                                     q    0       s             1     L

q   ⊔   s           ⊔  L                                    q    ⊔   s           ⊔  L

Problem 4 (25 points) Tint. To be submitted separately

Let Σ = {a,b,c}.  Design an iterator for Σ* , i.e., a one-way Turing machine with input alphabet Σ, that on input any string w ∈ Σ* , outputs the string next(w) that follows w in shortlex order. In the end configuration:

– the tape content consists of next(w) beginning in the first cell (all other cells blank)

– the head is under the first cell

– the state is qaccept

Problem 5 (10 points) Tint. To be submitted separately

Define a Turing machine with input alphabet {0, 1} that decides the language described by the regular expression

0(01)* 1

Problem 6 (10 points) Tint. To be submitted separately

Define a Turing machine with input alphabet {0, 1} that decides

{0i 1j  | 0 < i < j}

Problem 7 (10 points) Tint. To be submitted separately

Define a Turing machine with input alphabet {0, 1} that decides

{0n 13n  | n > 0}

Problem 8 (10 points) Tint. To be submitted separately

Define a Turing machine with input alphabet {a,b,c} that decides

{w cw | w ∈ {a,b}* }

Problem 9 (10 points) Tint. To be submitted separately

Define a Turing machine with input alphabet {0, 1} that decides

{1i 01j 01k  | i,j, k > 0 and k = i · j}