please explain Transitions that read a character off the input are very tiresome
ID: 3863436 • Letter: P
Question
please explain
Transitions that read a character off the input are very tiresome, so we want to allow "breaks" between them. I want every accepting computation of every string to consist of at least 1 transition between each character read from the input (I'm not worried about what happens on the stack here). Call these machines HPDAs. What is the relation between the class of languages PDAs recognize and those that HPDAs recognize? They are exactly the same. They have no languages in common. Every language a PDA recognizes, a HPDA also recognizes, but not vice versa. Every language a HPDA recognizes, a PDA also recognizes, but not vice versa. There are languages in common, but some languages a PDA can recognize and a HPDA cannot, and vice versa.Explanation / Answer
Answer:
Because HPDA is generalization of PDA , every PDA can be converted or we can say that simulated to PDA but the converse doesn not hold . That is whty there might be the chances that PDA can recognise but HPDA can not.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.