retagged by
1,881 views
1 votes
1 votes

retagged by

1 Answer

2 votes
2 votes
Answer: (a)

The Power of Push Down Automata (PDA) lies in its storage structure STACK. It overcomes the limitations of FA of finite memory by introducing a stack with infinite capacity and thus recognize a new set of languages called Context Free Languages.

However, if the stack of the PDA is restricted to a finite capacity, it will be as good as any finite state machine. In a very intuitive sense, we can realize why this is true. Consider a CFL which is not a regular language like $L={a^nb^n}$ and try to create a PDA (or DPA as per the questions) with a finite stack. We see that there is no way to ensure that the number of a's is equal to number of b's in the input string without storing the number of a's until we encounter first 'b'.

However, this is not a mere intuition that the finite stack PDA is equivalent to  Finite State machine. This can be proved with vigorousness. The basic idea of the proof is to create a Finite State machine that can simulate the behavior of finite stack PDA.

HTH

Related questions

1 votes
1 votes
0 answers
4
Matrix asked Jul 28, 2018
1,501 views
Is this approach of acceptance by empty stack correct ?I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.