pda to accept the language L={a^n b^m | n<m}

Question

I know how to solve for m<n but I'm struggling to understand the logic for m>n.

In m<n we push all a's in the stack and when we get b we popped out one a, when the input ends with a stack containing m-n a's the machine should enter the final state

How can I do for m>n....

Answer 1

The intial configuration is the same. But you've got two separate states for reading 'b's:

• State B1: I'm popping 'b's, but the stack hasn't been empty.

  • If the top of the stack is an 'a' and you read a 'b': stay in that state
  • If the stack is empty and you read a 'b': go to state B2

• State B2: I'm popping 'b's, and the stack is empty.

  • If the top of the stack is empty and you read a 'b', stay in that state
  • Otherwise fail.

You've read more b's than a's if you're in state B2.

Answer 2

The strings which are generated by the given language are as follows −

L={a,abb,aabbbb,aaabbbbbb,….}

Here no. of a’s are less than no. of b’s

Whenever ‘a’ comes, push 'a', When ‘b’ comes then pop one ‘a’ from the stack each time. For further input 'b' leave like that. Finally at the end of the string, if nothing is left in the STACK, then we can declare that language is accepted in the PDA.

The PDA for the problem is as follows − Transition functions The transition functions are as follows −

Step 1: δ(q0, a, Z) = (q0, aZ)

Step 2: δ(q0, a, a) = (q0, aa)

Step 3: δ(q0, b, a) = (q1, ε)

Step 4: δ(q1, b, a) = (q1, ε)

Step 5: δ(q1, b, Z) = (qf, Z)

Explanation Step 1 − Consider input string: "abb" which satisfies the given condition.

Step 2 − Scan string from left to right.

Step 3 − For input 'a' and STACK alphabet Z, then push 'a' into the stack.

Step 4 − For input 'b' and STACK alphabet 'a', then

Pop one 'a' from STACK: (b,a/ε) and state will be q1.

Step 5 − For any no. of input 'b' and top of the stack Z and state q1, then move to final state qf.

Step 6− We reached end of the string, for input ε and STACK alphabet Z,

Go to final state(qf): (ε, Z/Z)