please explain Stacks have been getting very expensive lately! I want to limit t
ID: 3863438 • Letter: P
Question
please explain
Stacks have been getting very expensive lately! I want to limit the stack size of a PDA to be at most 25 to save cost; call the machines that have this property RPDAs. This model works exactly as a normal PDA does, but if the stack has height 25 and on the next transition does not pop and does push, the computation immediately stops. What is the relation between the class of languages PDAs recognize and those that RPDAs recognize? They are exactly the same. They have no languages in common. Every language a PDA recognizes, a RPDA also recognizes, but not vice versa. Every language a RPDA recognizes, a PDA also recognizes, but not vice versa. There are languages in common, but some languages a PDA can recognize and a RPDA cannot, and vice versa.Explanation / Answer
D part is true, which is "Every language RPDA recognize are recognized by PDA"
It's because of the limited stack space in RPDA which is restricted to 25, if the size occupation is more than 25 then also the language will be recognized by the PDA but RPDA only recognize those who are in the language as well as they are taking stack space of only 25.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.