Solutions to Problem Set #5, CS 154, Spring 2012

Solutions to Problem Set #5

CS 154
May 14, 2012

Using the construction given in class gives a PDA with start state q₀, final state q₂, and a transition function δ as defined below.

  
δ(q₀, λ, z) = {(q₁, Sz)}  
δ(q₁, λ, S) = {(q₁, a), (q₁, b), (q₁, aXa), (q₁, bXb)}
δ(q₁, λ, X) = {(q₁, λ), (q₁, aX), (q₁, bX)}  
δ(q₁, a, a) = {(q₁, λ)}  
δ(q₁, b, b) = {(q₁, λ)}  
δ(q₁, λ, z) = {(q₂, z)}

The CFG for the PDA has start symbol S and rules below:

S → [q₀, z, q_f]

[q₀, z, q₀] → a[q₀, a, q₀][q₀, z, q₀]
[q₀, z, q₁] → a[q₀, a, q₀][q₀, z, q₁]
[q₀, z, q_f] → a[q₀, a, q₀][q₀, z, q_f]
[q₀, z, q₀] → a[q₀, a, q₁][q₁, z, q₀]
[q₀, z, q₁] → a[q₀, a, q₁][q₁, z, q₁]
[q₀, z, q_f] → a[q₀, a, q₁][q₁, z, q_f]
[q₀, z, q₀] → a[q₀, a, q_f][q_f, z, q₀]
[q₀, z, q₁] → a[q₀, a, q_f][q_f, z, q₁]
[q₀, z, q_f] → a[q₀, a, q_f][q_f, z, q_f]

[q₀, a, q₀] → a[q₀, a, q₀][q₀, a, q₀]
[q₀, a, q₁] → a[q₀, a, q₀][q₀, a, q₁]
[q₀, a, q_f] → a[q₀, a, q₀][q₀, a, q_f]
[q₀, a, q₀] → a[q₀, a, q₁][q₁, a, q₀]
[q₀, a, q₁] → a[q₀, a, q₁][q₁, a, q₁]
[q₀, a, q_f] → a[q₀, a, q₁][q₁, a, q_f]
[q₀, a, q₀] → a[q₀, a, q_f][q_f, a, q₀]
[q₀, a, q₁] → a[q₀, a, q_f][q_f, a, q₁]
[q₀, a, q_f] → a[q₀, a, q_f][q_f, a, q_f]

[q₀, a, q₀] → [q₁, a, q₀]
[q₀, a, q₁] → [q₁, a, q₁]
[q₀, a, q_f] → [q₁, a, q_f]

[q₁, a, q₁] → h

[q₁, a, q₀] → a[q₁, a, q₀][q₀, a, q₀]
[q₁, a, q₁] → a[q₁, a, q₀][q₀, a, q₁]
[q₁, a, q_f] → a[q₁, a, q₀][q₀, a, q_f]
[q₁, a, q₀] → a[q₁, a, q₁][q₁, a, q₀]
[q₁, a, q₁] → a[q₁, a, q₁][q₁, a, q₁]
[q₁, a, q_f] → a[q₁, a, q₁][q₁, a, q_f]
[q₁, a, q₀] → a[q₁, a, q_f][q_f, a, q₀]
[q₁, a, q₁] → a[q₁, a, q_f][q_f, a, q₁]
[q₁, a, q_f] → a[q₁, a, q_f][q_f, a, q_f]

[q₁, z, q_f] → λ

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

[q₁, a, q₁], [q₁, z, q_f] and
[q₀, a, q₁], [q₁, a, q_f] and
[q₀, a, q_f], [q₀, z, q_f] and
S

Eliminating other nonterminals gives

S → [q₀, z, q_f]
[q₀, z, q_f] → a[q₀, a, q₁][q₁, z, q_f]
[q₀, a, q₁] → a[q₀, a, q₁][q₁, a, q₁]
[q₀, a, q₁] → [q₁, a, q₁]
[q₀, a, q_f] → [q₁, a, q_f]
[q₀, a, q_f] → a[q₀, a, q₁][q₁, a, q_f]
[q₁, a, q₁] → h
[q₁, a, q₁] → a[q₁, a, q₁][q₁, a, q₁]
[q₁, a, q_f] → a[q₁, a, q₁][q₁, a, q_f]
[q₁, z, q_f] → λ

If [q₀, z, q_f] 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

The TM accepts those strings beginning with b, or with a prefix of the form {a^pb^qc^r | 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
  q₀aabbcc ⊢ Xq₁abbcc ⊢ Xaq₁bbcc ⊢ XaYq₂bcc ⊢ XaYbq₂cc ⊢ XaYq₃bZc ⊢ Xaq₃YbZc ⊢ Xq₃aYbZc ⊢ q₃XaYbZc ⊢ Xq₀aYbZc ⊢ XXq₁YbZc ⊢ XXYq₁bZc ⊢ XXYYq₂Zc ⊢ XXYYZq₂c ⊢ XXYYq₃ZZ ⊢ XXYq₃YZZ ⊢ XXq₃YYZZ ⊢ Xq₃XYYZZ ⊢ XXq₀YYZZ ⊢ XXYq₀YZZ ⊢ XXYYq₀ZZ ⊢ XXYYZq₅Z ⊢ XXYYZZq₅ ⊢
2. The computation on the second string is given below. It halts in a final state
  q₀aabbbcc ⊢ Xq₁abbbcc ⊢ Xaq₁bbbcc ⊢ XaYq₂bbcc ⊢ XaYbq₂bcc ⊢ XaYbbq₂cc ⊢ XaYbq₃bZc ⊢ XaYq₃bbZc ⊢ Xaq₃YbbZc ⊢ Xq₃aYbbZc ⊢ q₃XaYbbZc ⊢ Xq₀aYbbZc ⊢ XXq₁YbbZc ⊢ XXYq₁bbZc ⊢ XXYYq₂bZc ⊢ XXYYbq₂Zc ⊢ XXYYbZq₂c ⊢ XXYYbq₃ZZ ⊢ XXYYq₃bZZ ⊢ XXYq₃YbZZ ⊢ XXq₃YYbZZ ⊢ Xq₃XYYbZZ ⊢ XXq₀YYbZZ ⊢ XXYq₀YbZZ ⊢ XXYYq₀bZZ ⊢ XXYYbq₄ZZ
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
  q₀abbcc ⊢ Xq₁bbbc ⊢ XYq₂bcc ⊢ XYbq₂cc ⊢ XYq₃bZc ⊢ Xq₃YbZc ⊢ q₃XYbZc ⊢ Xq₀YbZc ⊢ XYq₀bZc ⊢ XYbq₄Zc
4. The shortest accepted string is b.

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
```
q₁1001 ⊢ 1q₃001 ⊢ 1Xq₃01 ⊢ 1XXq₃1 ⊢ 1XX1q₃ ⊢ 1XXq₄1
```
Since there is no next move and q₄ 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
```
    δ(q₁, 1) = {(q₃, 1, R)
    δ(q₁, 0) = {(q₄, 0, R)
    δ(q₃, 1) = {(q₃, 1, R)
    δ(q₃, 0) = {(q₃, X, R)
    δ(q₃, □) = {(q₄, □, L)
    δ(q₄, X) = {(q₂, X, R)
```

One possible TM is given below. Here, corresponding symbols in each copy of x are marked (by replacing them with X).
State q₀ moves right, looking for the leftmost unmarked symbol before c. If it sees such a symbol, it marks it, and moves to q₁ or q₂ depending on whether it sees a 0 or a 1. If it instead sees a c, it moves to q₇ to check whether all symbols have been marked.
States q₁ and q₂ move right, looking for a c, and moving to states q₃ and q₄ respectively upon finding one.
States q₃ and q₄ move right, looking for an a or b respectively. Upon finding one they mark it, move left, and enter state q₅.
State q₅ moves left to the c. Upon finding it, it moves to q₆.
State q₆ moves left to the (rightmost) X. It then moves right and enters q₀.
State q₇ moves right, expecting to see only X symbols before seeing a blank. Upon seeing a blank, it enters the final state q₈.

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

Solutions to Problem Set #5

CS 154May 14, 2012

CS 154
May 14, 2012