Construct nondeterministic pushdown automata that accept the

Construct nondeterministic pushdown automata that accept the following language:

{w | w over {a,b}* and w has the same number of a\'s and b\'s}

Solution

Let us consider that language L has a string w. In the string one of three conditions holds at any point:

Now we will use stack to calculate the number of a’s or b’s (whichever seen more in number).

1. Whenever we notice the same number of characters, we terminate both characters by consuming the input and popping the stack.

2. Whenever we notice more number of a’s, there will be a\'s on the stack.

3. Whenever we notice more number of b\'s there will be b\'s on the stack.

As discussed in point (1) whenever the count of numbers of a’s and b’s are even, the stack will be empty. And further we will start from the character whichever comes next (suppose a is the next character after stack is empty, we will push a and count for a will be 1).

Push Down Automata (PDA) will be:

(Count of a’s till now seen) - (count of b’s till now seen)

= (count of a’s on stack) - (count of b\'s on stack)

Here w L iff, we have finished reading w,

[(Count of a\'s till now) - (Count of b\'s till now)] = 0.

Let S is build in order that it continues above statement, in that S consumes w and it results stack=0 (Stack is empty) it has seen string w in L. If the case is: stack! =0 (Stack is not empty), in that case it has not seen string w in L.

To build this language we have to get the resulted stack as empty, which is the case where we might have to push either a or b. We will take a special character $ by pushing it in bottom of stack. This special character $ will symbolize that the stack is empty. We cannot use to symbolize the empty stack because this symbol always matches even when the stack is not empty.

There will be two states:

State 1: (start state) push $ and go to working state

State 2: (final state) when we popped $.

S = ({d, w, g}, {a, b}, {$, a, b}, p, d, {g}),

where p = { ((d, , ), (w, $))       /* state 1: push $ */

((w, a, $), (w, a$))            /* stack= empty, next is a, so push a */

((w, a, a), (w, aa))            /* count number of a\'s*/

((w, b, a), (w, ))             /* count number of a\'s, next is b, so cancel a and b */

((w, b, $), (w, b$))          /* stack=empty and next is b, push b */

((w, b, b), (w, bb))           /*counting b\'s, next is b. push b */

((w, a, b), (w, ))              /*counting b\'s,next is a, cancel b and a */

((w, , $), (g, ))}              /*stack= empty of a\'s and b\'s. Pop $ and quit. */