L 1= {an bn+m cm | n ≥ 0, m ≥ 1}

Question

Given ∑ = {a, b, c}, consider the language L 1= {aⁿ b^n+m c^m | n ≥ 0, m ≥ 1}

L2 = {aⁿ b^mc^n+m | n ≥ 0, m ≥ 1}
Which one of the following is incorrect?

1.   The language L 1 shall have 6 states in its equivalent PDA
2.   The language L1 is not DCFL.
3.  The language L1 requires an NPDA for its acceptance.
4. The language L2 is DCFL

Comments

i think both L1 and L2 are DCFL.

for L2,just push a and b and for every 'c',pop every 'b' till 'b' is finished and then pop evry 'a'.after completing string,if there is still any letter on stack then,not accepeted.

for L1,just push a on to the stack,now,for  'b' pop 'a' from the stack till 'a' is finished.then for all the 'b' remaining,push 'b' onto the stack,then for every 'c',pop 'b' from the stack..

am i correct??so they are DCFLs..right??

---

you are correct ..both are dcfl's.

Answer 1

For L1:

1. push a's until b appears. When b comes change the state and start popping out a's.

2.Repeat the same procedure until Z₀ appears. When Z₀ comes start pushing b's again.

3.When c comes, on each arrival of c pop b from stack.

4.At the end Z₀ remains on the stack and if ϵ comes then string is accepted.

As the above mentioned procedure is Deterministic L1 is DCFL.

Correct Ans :2(as the statement is incorrect)

Answer 2

option 2 is wrong because L1 and L2 are DCFL

Comments

will the PDA have 6 states?