Mumbai University > Information Technology > Sem 4 > Automata Theory

Marks: 10M

We find here that the number of a‟s surrounding the b‟s have the same number of occurences while number of b‟s can vary independent of number of a‟s.

Assuming m=3,n=2

The sample string will be aabbbaa

For a Push Down Automata, the final state is reached when the stack is empty once the whole string has been processed, and hence we need some kind of symmetry in the language to be processed to ensure corresponding pop operations occur for every push operation

As we see in this example the number of occurrence of the character „b‟ may not be the same as that of character „a‟

So, to construct a PDA in this example, it would be better that „b; be treated as a kind of delimiter rather than an element to be pushed onto the stack i.e. whenever we encounter „b‟, we shall not perform any specific, thus treating „b‟ as a mere separator between the starting and ending two an

Claim:

Once we encounter the first an sequence, we push „a‟ elements into the stack. Then, when we encounter „b‟, we shall not perform any operation. And after the sequence of „b‟ is over and we encounter the trailing an , we shall pop the elements out.

At the end of the string processing activity, we find that „b‟ was used merely as a separator between the first and last an sequence and by using „b‟ that way, the stack is empty eventually.

Stack operations:

δ(S,a,z0)=(S,az0) (az0 pushed into stack)

δ(S,a,a)=(S,aa) (aa pushed into stack)

δ(A,b,a)=(A) (no operation)

δ(A,a,az0)=(A, є) (a is popped from the stack)

δ(A, є,z0)=(Q, z0) (Stack empty condition)