CSCI435 Home Assignment 5 Solved

35.00 $ 17.50 $

Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . zip solution files instantly, after Payment


5/5 - (1 vote)

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.