## Description

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* | *n _{a}*(

*w*) +

*n*(

_{b}*w*) =

*n*(

_{c}*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.

- L
_{1}= {*bba***bab** } - L
_{2}= {*bbb*aba*} - optional] L
_{4}= L_{2}– L_{1}.

Q3. Give the language that is accepted by the NPDA M in a formal expression (including a regular expression) where M = ({*q _{0}, q_{1}, q_{2}*}, {

*a, b*}, {

*a, b*, z}, d,

*q*, z, {

_{0}*q*,

_{0}*q*,

_{1}*q*}), with transitions

_{2}¨ d(*q _{0}*,

*a*, z) = {(

*q*,

_{1}*a*), (

*q*, l)},

_{2}¨ d(*q _{1}*,

*b*,

*a*) = {(

*q*,

_{1}*b*)},

¨ d(*q _{1}*,

*b*,

*b*) = {(

*q*,

_{1}*b*)},

¨ d(*q _{1}*,

*a*,

*b*) = {(

*q*, l)},

_{2}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 ®
*ab*S*b*| 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 = ({*q _{0}, q_{1}*}, {

*a, b*}, {

*A*, z}, d,

*q*, z, {

_{0}*q*}), with the transitions

_{1}¨ d(*q _{0}*,

*a*, z) = {(

*q*,

_{0}*Az*)},

¨ d(*q _{0}*,

*b*,

*A*) = {(

*q*,

_{0}*AA*)},

¨ d(*q _{0}*,

*a*,

*A*) = (

*q*, l).

_{1}Simplify the production rules by eliminating the useless variables and productions.

Q6. Construct a Deterministic-PDA that accepts L= { *a ^{n}b^{m}* | 0 £

*m*<

*n*} to show L is a Deterministic-CFL.