GATE CSE 2002 | Question: 1.7

Question

The language accepted by a Pushdown Automaton in which the stack is limited to $10$ items is best described as

• A. Context free
• B. Regular
• C. Deterministic Context free
• D. Recursive

Answer 1

Correct Option: B

With only finite positions in stack, we can have only finite configurations and these can also be modeled as states in a finite automata.

Comments

Yes, we have finite configurations in stack. We can make a DFA with same power, simply replicating each configuration with new state. And
For every DFA, We have such PDA (Simply don't use stack at all)
Hence this PDA is equivalent to DFA.

---

Hi,

I have a doubt here. Consider the language A^n B^n where n<10. This is context free language which can be accepted by PDA with 10 length stack but not a DFA?

---

@avraw

Hey, you can easily make the NFA accepting all the string in a^nb^n where n < = 10.

Make initial state accepting, then make a state accepting which can accept ab, then make the state accepting which can accept aabb and so on for other string in the language.

Now you can convert this NFA to DFA.

---

@avraw

We can construct DFA for a^nb^n for n<10 as it is regular

---

As there is a finite number of items mentioned that is 10 items. So, a FA is always possible. That’s why regular language is best described.

Can we say conclude this answer with the above statement?

---

@Sachin Mittal 1, 

using this approach, we will have at most 10 states, Finite State automata which generates Regular Grammar. please verify.