If L is any language accepted by DPDA with stack containing only one symbol. Then L can be

Question

Comments

all options r true

---

Option a  if it is regular then it can be cgl CSL dcfl

---

This question seems ambiguous to me. Because it doesn't clearly state whether the stack can only STORE one symbol or USE one symbol.

And the answer will vary in both, because if stack is of finite size then the language is regular, but if it says that the stack can store only one symbol then it will be DCFL.

Please someone clarify.

Answer 1

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

Comments

Right....Thanks Prateek

---

sorry i thought the string is accepted at a point where a symbol was remaining in stack.