41 votes 41 votes The language accepted by a Pushdown Automaton in which the stack is limited to $10$ items is best described as Context free Regular Deterministic Context free Recursive Theory of Computation gatecse-2002 theory-of-computation easy identify-class-language + – Kathleen asked Sep 15, 2014 edited Feb 20, 2018 by kenzou Kathleen 8.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 50 votes 50 votes 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. Arjun answered Jun 6, 2015 edited May 6, 2021 by soujanyareddy13 Arjun comment Share Follow See all 6 Comments See all 6 6 Comments reply Sachin Mittal 1 commented Dec 27, 2016 reply Follow Share 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. 27 votes 27 votes avraw commented May 3, 2020 reply Follow Share 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 votes 0 votes Rijul commented May 23, 2020 reply Follow Share @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. 1 votes 1 votes Pathki Shivamsh commented Aug 26, 2020 reply Follow Share @avraw We can construct DFA for a^nb^n for n<10 as it is regular 0 votes 0 votes ankit3009 commented Nov 18, 2021 reply Follow Share 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? 0 votes 0 votes Shakyaji commented Dec 16, 2021 reply Follow Share @Sachin Mittal 1, using this approach, we will have at most 10 states, Finite State automata which generates Regular Grammar. please verify. 0 votes 0 votes Please log in or register to add a comment.