The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.7k views

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
asked in Theory of Computation by Veteran (59.6k points)
edited by | 1.7k views

1 Answer

+23 votes
Best answer

B. Regular.

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

answered by Veteran (362k points)
edited by
+9
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.
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,416 questions
48,474 answers
154,484 comments
62,893 users