CECS 329 Writing Assignment 5
Problems
A. Given the sequence of PDA configuration triples
(c, , ),(d, , x),(b, , xx),(c, 0, x),(d, 1, ),(d, 1, x),
(a, 1, xx),(c, 0, xxx),(d, 1, xx),(b, 0, x),(a, , ),
where the first component is the current state, the second is the input symbol that is read,
and the third component is the stack contents. Use this sequence to provide a portion of the
natural CFG for the associated PDA and use it to derive the word 0111010. (10 pts)
1
B. Consider the language
L = {x = y + z|x, y, z ∈ {0, 1}
+ and x + y = z}.
For example 101 = 11 + 10 ∈ L since
(5)2 = (3)2 + (2)2.
Use the CFL Pumping Lemma to prove that L is not a CFL. Hint: you may assume that two
binary numbers w1 and w2, each with leading ones, have the same numerical value iff w1 = w2,
i.e. iff they both represent the same binary word. This is useful when both sides of the equality
symbol are being simultaneously pumped. (10 pts)
2
