PDA to accept a language of strings containing mor

Question

Produce a PDA to recognise the following language : the language of strings containing more a's than b's

I have been struggling with this question for several days now, I seem to have hit a complete mental block. Would any one be able to provide some guidance or direction to how I can solve this problem?

Answer 1

I'm assuming you mean strings of the form a^nb^m, where n>m.

The idea is relatively easy, for a you push it on the stack (in a loop), for b you switch to a separate loop to pop a from the stack. If the stack is ever empty, you give up with a FAIL. If in the first loop you get anything other than a or b, or in the second loop you get anything other than b, you give up with FAIL.

At the end you try to pop another a and if the stack is empty you give up with a FAIL (ie, you had at least as many b's as a's on the stack, possibly more). If not, SUCCESS.

Edit: As a side note, I'm not convinced this is the right site for this question, might be better on programmers. Not sure though so not voting to close.

Answer 2

Your problem of "more a's than b's" can be solved by PDA.

All you have to do is:

• When input is a and the stack is either empty or has an a on the top, push a on the stack; pop b, if b is the top.

• When input is b and the stack is either empty or has an b on the top, push b on the stack; pop a, if a is on the top.

• Finally, when the string is finished, go to the final state with null input if a is on top of the stack. Otherwise you don't have more a's than b's.

Answer 3

Basic infromation of transaction is given in below figure.

Here is the complete transaction.

In it є is equal to NULL. $ sign is pushed into stack at the start of the string and pop at the end to determine the string has been completely read and end now. qo is start state and q5 is final state

It is Non-deterministic push down Automata (NPDA).So Due to NPDA the transaction of rejection string is not shown in it.

Answer 4

I have come up with a more general solution to the problem concerning the number of as and bs, see the picture below:

where a > b means more as than bs and so does a < b , a = b.

Z means the bottom of stack, and A/B are stack symbols.

I'm excited about it because this PDA seperates the 3 different states. In your problem, you can just set the a > b state to be the final state and let a = b be the start state.

And if you want to step further, you can use this PDA to easily generate PDAs for a >= b, a - b >= 1, 2 <= a - b <= 3 etc, which is fascinating.