PDA to accept a language of strings containing more a's than b's

automata formal-languages pushdown-automaton
user1301430 picture user1301430 · Mar 29, 2012 · Viewed 16.4k times · Source

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

Divyanjali picture Divyanjali · Sep 11, 2012

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.

Related questions

Design DFA accepting binary strings divisible by a number 'n'

I need to learn how to design a DFA such that given any number 'n', it accepts binary strings {0, 1} whose decimal equivalent number is divisible by 'n'. There will be different DFAs for different 'n', but can somebody give a …

Read More
Regular vs Context Free Grammars

I'm studying for my computing languages test, and there's one idea I'm having problems wrapping my head around. I understood that regular grammars are simpler and cannot contain ambiguity, but can't do a lot of tasks that are required for …

Read More
Finding the complement of a DFA?

I am asked to show DFA diagram and RegEx for the complement of the RegEx (00 + 1)*. In the previous problem I had to prove that the complement of a DFA is closed and is a regular expression also, so I know …

Read More