## Solutions to Problem Set #5

### CS 154May 14, 2012

1. Using the construction given in class gives a PDA with start state q0, final state q2, and a transition function δ as defined below.

```
δ(q0, λ, z) = {(q1, Sz)}
δ(q1, λ, S) = {(q1, a), (q1, b), (q1, aXa), (q1, bXb)}
δ(q1, λ, X) = {(q1, λ), (q1, aX), (q1, bX)}
δ(q1, a, a) = {(q1, λ)}
δ(q1, b, b) = {(q1, λ)}
δ(q1, λ, z) = {(q2, z)}
```

2.

3. The CFG for the PDA has start symbol S and rules below:
```S → [q0, z, qf]

[q0, z, q0] → a[q0, a, q0][q0, z, q0]
[q0, z, q1] → a[q0, a, q0][q0, z, q1]
[q0, z, qf] → a[q0, a, q0][q0, z, qf]
[q0, z, q0] → a[q0, a, q1][q1, z, q0]
[q0, z, q1] → a[q0, a, q1][q1, z, q1]
[q0, z, qf] → a[q0, a, q1][q1, z, qf]
[q0, z, q0] → a[q0, a, qf][qf, z, q0]
[q0, z, q1] → a[q0, a, qf][qf, z, q1]
[q0, z, qf] → a[q0, a, qf][qf, z, qf]

[q0, a, q0] → a[q0, a, q0][q0, a, q0]
[q0, a, q1] → a[q0, a, q0][q0, a, q1]
[q0, a, qf] → a[q0, a, q0][q0, a, qf]
[q0, a, q0] → a[q0, a, q1][q1, a, q0]
[q0, a, q1] → a[q0, a, q1][q1, a, q1]
[q0, a, qf] → a[q0, a, q1][q1, a, qf]
[q0, a, q0] → a[q0, a, qf][qf, a, q0]
[q0, a, q1] → a[q0, a, qf][qf, a, q1]
[q0, a, qf] → a[q0, a, qf][qf, a, qf]

[q0, a, q0] → [q1, a, q0]
[q0, a, q1] → [q1, a, q1]
[q0, a, qf] → [q1, a, qf]

[q1, a, q1] → h

[q1, a, q0] → a[q1, a, q0][q0, a, q0]
[q1, a, q1] → a[q1, a, q0][q0, a, q1]
[q1, a, qf] → a[q1, a, q0][q0, a, qf]
[q1, a, q0] → a[q1, a, q1][q1, a, q0]
[q1, a, q1] → a[q1, a, q1][q1, a, q1]
[q1, a, qf] → a[q1, a, q1][q1, a, qf]
[q1, a, q0] → a[q1, a, qf][qf, a, q0]
[q1, a, q1] → a[q1, a, qf][qf, a, q1]
[q1, a, qf] → a[q1, a, qf][qf, a, qf]

[q1, z, qf] → λ
```

Although the answer above is correct and complete, it's not clear that it is correct. Some simplification will help to see that it generates the same language that the PDA accepts, namely the set of strings over {a,h} with the same number of a's as h's, and for which each proper prefix has more a's than h's. The nonterminal symbols that generate strings of terminals are

```[q1, a, q1], [q1, z, qf] and
[q0, a, q1], [q1, a, qf] and
[q0, a, qf], [q0, z, qf] and
S```

Eliminating other nonterminals gives

```S → [q0, z, qf]
[q0, z, qf] → a[q0, a, q1][q1, z, qf]
[q0, a, q1] → a[q0, a, q1][q1, a, q1]
[q0, a, q1] → [q1, a, q1]
[q0, a, qf] → [q1, a, qf]
[q0, a, qf] → a[q0, a, q1][q1, a, qf]
[q1, a, q1] → h
[q1, a, q1] → a[q1, a, q1][q1, a, q1]
[q1, a, qf] → a[q1, a, q1][q1, a, qf]
[q1, z, qf] → λ```

If [q0, z, qf] is relabeled as S and other states relabeled so that the left-hand sides above are respectively S, X, X, Y, Y, H, Z, and L, the rules become

```S → aXL
X → aXH | H
Y → Z | ahZ
H → h | aHH
Z → ahL
L → λ
```
This grammar can be further simplified by eliminating Y and Z as unreachable, and then substituting for L to give
```S → aX
X → aXH | H
H → h | aHH
```
Note that strings generated by H and X have exactly one more h than a, so that strings generated by S have the same number of a's as h's. For example the string aahahh may be derived as
S ⇒ aX ⇒ aaXH ⇒ aaHH ⇒ aahH ⇒ aahaHH ⇒ aahahH ⇒ aahahh

4. The TM accepts those strings beginning with b, or with a prefix of the form {apbqcr | 0<p ≤q and 0<p≤r and (p<q or p<r) } So the second string should be accepted, but not the first.
1. The computation on the first string is given below. It halts in a nonfinal state
``` q0aabbcc ⊢ Xq1abbcc ⊢ Xaq1bbcc ⊢ XaYq2bcc ⊢ XaYbq2cc ⊢ XaYq3bZc ⊢ Xaq3YbZc ⊢ Xq3aYbZc ⊢ q3XaYbZc ⊢ Xq0aYbZc ⊢ XXq1YbZc ⊢ XXYq1bZc ⊢ XXYYq2Zc ⊢ XXYYZq2c ⊢ XXYYq3ZZ ⊢ XXYq3YZZ ⊢ XXq3YYZZ ⊢ Xq3XYYZZ ⊢ XXq0YYZZ ⊢ XXYq0YZZ ⊢ XXYYq0ZZ ⊢ XXYYZq5Z ⊢ XXYYZZq5 ⊢ ```
2. The computation on the second string is given below. It halts in a final state
``` q0aabbbcc ⊢ Xq1abbbcc ⊢ Xaq1bbbcc ⊢ XaYq2bbcc ⊢ XaYbq2bcc ⊢ XaYbbq2cc ⊢ XaYbq3bZc ⊢ XaYq3bbZc ⊢ Xaq3YbbZc ⊢ Xq3aYbbZc ⊢ q3XaYbbZc ⊢ Xq0aYbbZc ⊢ XXq1YbbZc ⊢ XXYq1bbZc ⊢ XXYYq2bZc ⊢ XXYYbq2Zc ⊢ XXYYbZq2c ⊢ XXYYbq3ZZ ⊢ XXYYq3bZZ ⊢ XXYq3YbZZ ⊢ XXq3YYbZZ ⊢ Xq3XYYbZZ ⊢ XXq0YYbZZ ⊢ XXYq0YbZZ ⊢ XXYYq0bZZ ⊢ XXYYbq4ZZ ```
3. Three strings of length 5 fitting the description above are those beginning with b, as well as `abbbc`, `abbca`, `abbcb`, `abbcc`, `abcca`, `abccb`, and `abccc`. The accepting computation for `abbcc` is
``` q0abbcc ⊢ Xq1bbbc ⊢ XYq2bcc ⊢ XYbq2cc ⊢ XYq3bZc ⊢ Xq3YbZc ⊢ q3XYbZc ⊢ Xq0YbZc ⊢ XYq0bZc ⊢ XYbq4Zc ```
4. The shortest accepted string is `b`.

5. The universal TM would halt but not accept. It would simulate the TM with transition function below on the input string 1001. The computation would be
`q11001 ⊢ 1q3001 ⊢ 1Xq301 ⊢ 1XXq31 ⊢ 1XX1q3 ⊢ 1XXq41`
Since there is no next move and q4 is not a final state, the TM would halt but not accept.

The TM represents a slightly awkward way of accepting the language represented by the regular expression 0(0+1)*1. Its moves are

```    δ(q1, 1) = {(q3, 1, R)
δ(q1, 0) = {(q4, 0, R)
δ(q3, 1) = {(q3, 1, R)
δ(q3, 0) = {(q3, X, R)
δ(q3, □) = {(q4, □, L)
δ(q4, X) = {(q2, X, R)
```
6. One possible TM is given below. Here, corresponding symbols in each copy of `x` are marked (by replacing them with `X`).

State q0 moves right, looking for the leftmost unmarked symbol before `c`. If it sees such a symbol, it marks it, and moves to q1 or q2 depending on whether it sees a 0 or a 1. If it instead sees a `c`, it moves to q7 to check whether all symbols have been marked.
States q1 and q2 move right, looking for a `c`, and moving to states q3 and q4 respectively upon finding one.
States q3 and q4 move right, looking for an `a` or `b` respectively. Upon finding one they mark it, move left, and enter state q5.
State q5 moves left to the `c`. Upon finding it, it moves to q6.
State q6 moves left to the (rightmost) `X`. It then moves right and enters q0.
State q7 moves right, expecting to see only `X` symbols before seeing a blank. Upon seeing a blank, it enters the final state q8.

7.

grading scale: 34 A-, 30 B-, 26 C-, 22 D-