4

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?

nbro
  • 15,395
  • 32
  • 113
  • 196
user1301430
  • 189
  • 1
  • 2
  • 11

5 Answers5

8

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.

nbro
  • 15,395
  • 32
  • 113
  • 196
Divyanjali
  • 89
  • 1
  • 2
4

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

PDA for relations between as and bs

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.

youkaichao
  • 1,938
  • 1
  • 14
  • 26
0

PDA to accept more a's than b's

enter image description here

keikai
  • 14,085
  • 9
  • 49
  • 68
Padmaja Grandhe
  • 1
0

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.

Blindy
  • 65,249
  • 10
  • 91
  • 131
  • Your suggestion works if you have more a's infront of the b's and if the string ends with an a. However it fails when the string ends with a 'b' or if the string has 'b' infront of 'a' eg bbbaaaa would fail & baaaaab would also fail Any suggestions? – user1301430 Mar 29 '12 at 17:29
  • It does, yes, but then that language is no longer a CFG now is it? – Blindy Mar 29 '12 at 17:46
  • 1
    Thanks for your help, just one more question. What string variations will the PDA accept for this problem then, and what ones will it reject. I was under the assumption it could accept any variation of a's and b's as long as there were more a's in the string than b. Thanks – user1301430 Mar 29 '12 at 18:05
  • You tell me, it's your problem... For a CFG specifically though, to do the counting, you need a clear separation between the `a`'s and `b`'s (or if you get like `abbaa` you'll stack underflow on the 3rd character and you won't know if you have enough `a`'s coming up). – Blindy Mar 29 '12 at 18:10
-1

Basic infromation of transaction is given in below figure. enter image description here

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. enter image description here

Muhammad Kashif Arif
  • 648
  • 7
  • 17
  • 1
    What happens if the first symbol in the string is `b`? This does not accept strings of the form `b^ia^j` where `i < j`. Am I missing something? – solidstatejake Mar 20 '20 at 00:38
  • As per above comment, this doesn't handle the case if the input is b at first. – anddak Feb 27 '21 at 17:09