In any (N/D)PDA, assume that a start stack symbol z is already in the stack; so, you don’t have to insert z into the stack at the beginning of transition.
Q1. For a given language L = { w | na(w) + nb(w) = nc(w) } where S = G = {a, b, c}
- Construct a PDA M that accepts L with S = G = {a, b, c}
- Show the sequence of instantaneous descriptions for the acceptance of acacbcbc by M in 1).
- optional] Give a CFG G that generates L, L(G) = L.
Q2. Construct an NPDA for the following languages.
- L1 = {bba*bab* }
- L2 = {bbb*aba }
- optional] L4 = L2 – L1.
Q3. Give the language that is accepted by the NPDA M in a formal expression (including a regular expression) where M = ({q0, q1, q2}, {a, b}, {a, b, z}, d, q0, z, { q0 , q1, q2}), with transitions
¨ d(q0, a, z) = {(q1, a), (q2, l)},
¨ d(q1, b, a) = {(q1, b)},
¨ d(q1, b, b) = {(q1, b)},
¨ d(q1, a, b) = {(q2, l)},
Q4. (A) Construct a NPDA that accepts the language defined by the given grammar and (B) give the language in a formal expression (including a regular expression).
- S ® abSb | l.
- S ® AA | a, A ® SA | ab.
Hint: Convert the grammar into Greibach Normal Form, then apply Thm. 7.1.
Q5. Find a (minimal) Context-Free Grammar that generates the language accepted by the NPDA M where M = ({q0, q1}, {a, b}, {A, z}, d, q0, z, {q1}), with the transitions
¨ d(q0, a, z) = {(q0, Az)},
¨ d(q0, b, A) = {(q0, AA)},
¨ d(q0, a, A) = (q1, l).
Simplify the production rules by eliminating the useless variables and productions.
Q6. Construct a Deterministic-PDA that accepts L= { anbm | 0 £ m < n } to show L is a Deterministic-CFL.
