The University of Melbourne
School of Computing and Information Systems COMP30026 Models of Computation
Selected Tutorial Solutions, Week 11
90. Here are PDAs for the languages from Exercise 77.
(a) The language is regular, so a PDA will not need to use its stack at all. The result is very similar to a DFA seen in a lecture:
0, ε → ε
1, ε → ε
(b) Again, the language is regular—too easy:
(c) Odd-length strings with 0 in the middle: 0, ε → x
0, ε → ε
0, ε → ε
1, ε → ε
0, ε → ε
(d) Palindromes:
ε, ε → $
ε, ε → $
0, ε → ε
ε,$→ε
ε,$→ε
0, x → ε 1, x → ε
0, ε → 0
1,ε→1 ε,ε→ε 1,1→ε
0, ε → ε 1, ε → ε
1, ε → x
91. The first two PDAs were both progressive and deterministic. The last two were neither.
0, ε → ε
1, ε → ε
1, ε → ε 1, ε → ε
0, 0 → ε
0, ε → ε 1, ε → ε
0, ε → ε 1, ε → ε
92. For the case v ̸= ε we define
δ((qp,qd),v,x)=((rp,rd),y) (rp,y)∈δP(qp,v,x)∧rd =δD(qd,v)
But we must also allow transitions that don’t consume input, so: δ((qp,qd),ε,x) = ((rp,qd),y) (rp,y) ∈ δP(qp,ε,x)
93. (a)
Assume that A is context-free and let p be the pumping length. Consider the string apbpapbp ∈ A. The pumping lemma tells us that the string can be written uvxyz, with v and y not both empty, and with |vxy| ≤ p, such that uvixyiz ∈ A for all i. Clearly, if one (or both) of v and y contains an a as well as a b then pumping up will lead to a string that is not in A, as the result will have more than two substrings ab. So each of v and y must contain as only, or bs only, unless it is empty. If neither v nor y contains a b then both must come from the same ai segment (the first or the last), because |vxy| ≤ p; and then, when we pump up, that segment alone grows, while the other ai segment is untouched. Similarly, if neither v nor y contains an a. So in these cases the result of pumping is not in A. The only remaining cases are when v is from the first ai segment and y is from the first bj segment, or v is from the first bj segment and y is from the second ai segment, or v is from the second ai segment and y is from the second bj segment. In each case, pumping up will take the string outside A. We conclude that A is not context-free.
(b) Here is a context-free grammar for B:
S → T|aSb
T→ε|bTa
. (2, 1)
(2, 0) .
(1, 1) (1, 0)
. (0, 2)
(0, 1)
(0, 0)
(c) If we pick the obvious candidate string apbpapbp ∈ B, we fail to get a contradiction withthepumpinglemma. Namelywemighthavev=bk andy=ak (0