CSCI435-Assignment 5 Solved  

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. [20] For a given language L = { w | na(w) + nb(w) = nc(w) }  where S = G = {a, b, c}

(1)  [10] Construct a PDA M that accepts L with S = G = {a, b, c}

 

 

(2)  [10] Show the sequence of instantaneous descriptions for the acceptance of acacbcbc by M in 1).

 

A = push to stack 

C = delete A 

A = push to stack 

C = delete A 

B = push to stack 

C = delete B 

B = push to stack  

C = delete b 

 

Epsilon to Z0 

 

(3)  [10, optional] Give a CFG G that generates L, L(G) = L.

 

Anbmcn+m 

S - AC 

A- aAc | lambda 

C - cCb | lambda

Q2. [20] Construct an NPDA for the following languages.

(1)  [10] L1 = {bba*bab* }

 

 

(2)  [10] L2 = {bbb*aba }

 

 

(3)  [5, optional] L4 = L2 – L1.

 

L2 - (L1 ∩ L2)

But {L1 ∩ L2} = {bbaba}

So L2 – L1 = L2 - {bbaba} 

 

 

 

Q3. [10] 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)},  

 

 

So, q0 will have 2 transitions 

Q1 will consume any number of B’s 

Q2 is the state in which it accepts endings with an “a”

Regular Expression: a+abma

 

Q4. [20] (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).

(1)  S ® abSb | l.

(2)  S ® AA | a, A ® SA | ab.

Hint: Convert the grammar into Greibach Normal Form, then apply Thm. 7.1.

 

 

Q5. [20] 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.

δ(q0, a, z) = {(q0, Az)}, 

δ(q0, b, A) = {(q0, AA)},

δ(q0, a, A) = {(q1, λ)}, 

δ(q1, λ, A) = {(q1, λ)}, 

δ(q1, λ, z) = {(q2, λ)}.

 

Last three transition = 

(q0Aq1) → a, 

(q1Aq1) → λ, 

(q1zq2) → λ.

 

From the first two transitions =

(q0zq0) → a(q0Aq0)(q0zq0)|a(q0Aq1)(q1zq0)|a(q0Aq2)(q2zq0), 

(q0zq1) → a(q0Aq0)(q0zq1)|a(q0Aq1)(q1zq1)|a(q0Aq2)(q2zq1), 

(q0zq2) → a(q0Aq0)(q0zq2)|a(q0Aq1)(q1zq2)|a(q0Aq2)(q2zq2),

(q0Aq0) → a(q0Aq0)(q0Aq0)|a(q0Aq1)(q1Aq0)|a(q0Aq2)(q2Aq0),

(q0Aq1) → a(q0Aq0)(q0Aq1)|a(q0Aq1)(q1Aq1)|a(q0Aq2)(q2Aq1),

(q0Aq2) → a(q0Aq0)(q0Aq2)|a(q0Aq1)(q1Aq2)|a(q0Aq2)(q2Aq2).

 

Removing the useless variables: 

(q1zq0), (q1zq1), (q1zq2),(q2zq0), (q2zq1), (q2zq2), (q1Aq0), (q1Aq1), (q1Aq2), (q2Aq0), (q2Aq1), and (q2Aq2).

 

Thus equaling: 
(q0Aq1) → a, 

(q1Aq1) → λ, 

(q1zq2) → λ,

(q0zq0) → a(q0Aq0)(q0zq0),

 (q0zq1) → a(q0Aq0)(q0zq1), 

(q0zq2) → a(q0Aq0)(q0zq2), 

(q0Aq0) → a(q0Aq0)(q0Aq0), 

(q0Aq1) → a(q0Aq0)(q0Aq1), 

(q0Aq2) → a(q0Aq0)(q0Aq2),

 

Having the start variable as (q0zq2)

 

Q6. [10] Construct a Deterministic-PDA that accepts L= { anbm | 0 £ m < n } to show L is a Deterministic-CFL.

 

d(q0, a, z) = {(q0, az)}, 

d(q1, a, a) = {(q1, aa)}, 

d(q1, b, a) = (q2, l).

d(q2, b, a) = {(q0, l)}, 

d(q2, b, z) = {(q3, z)}, 

d(q3, b, z) = (q3, z).