in Theory of Computation edited by
5,530 views
31 votes

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

  1. Context free
  2. Regular
  3. Deterministic Context free
  4. Recursive
in Theory of Computation edited by
5.5k views

1 Answer

37 votes
 
Best answer

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.

edited by
by

4 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.
18
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?
0
@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.
0
@avraw

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

Related questions