CODEWITHSUNDEEP
computer-scienceautomatafinite-automatapushdown-automatonautomata-theory
largoLagrande
largoLagrande

Reputation: 11

How do I construct this pushdown automata following this rules

The rules are: It cant start by letter a. It cant finish by letter b. It must contain b=i a=2i. The alphabet is a,b. Ive tried do it empty the stack. But unfortunately I cant reach it. The input like this for example: bbaaaa its ok because for every b input I place in the stack 2 a and the a inputs removes the stack. But when the input is like this: baaabbaaa cant follow that steps. Any suggestion?

Upvotes: 1

Views: 592

Answers (1)

Patrick87
Patrick87

Reputation: 28302

My approach would be this:

Make the initial state accepting (since the empty string satisfies the language criteria) and have a single transition to another state on b. Push two b onto the stack as part of this transition. The PDA will crash and reject if it sees a in the initial state.

This other state we've transitioned to corresponds to having just seen b. Because our string cannot end in b, this state cannot be accepting. If we see another b here, we can loop back to this state and add two more b to the stack each time (if there are b on top of the stack) or else cancel two a (if there are two a) or replace a with b (if the stack has just one a). If we see an a, we must go to a new state, and we should pop a b off the stack (if there are b) or push another a (if a is on top).

The third state means we last saw an a, so if we run out of input here with an empty stack, we should accept. If we see a we can stay and pop b (if b is on top) or push a (if a is on top). If we see b, we should return to the second state and push two b, pop two a, or pop a and push b, depending on the stack contents.

Our stack keeps track of the number of additional symbols that the PDA must see to clear the stack as follows:

  • the stack will only ever contain either a or b at one time, never both together
  • if we have seen n a and m b and n = 2m, the stack will be empty
  • if we have seen n a and m b and n > 2m, the stack will have n - 2m a in it
  • if we have seen n a and m b and n < 2m, the stack will have 2m - n b in it

Upvotes: 1

Related Questions