האם PDA יכול לקבל מלה גם אם המחסנית לא ריקה כאשר הוא מגיע למצב מקבל ?
Date: 16 Apr 2010 02:14
Number of posts: 3
RSS: New posts
I think (but have to say not sure) that in class we said that the stack need not be empty so long as the state is accepting.
The important point is though that one can (pretty easily) show (a good exercise!) that the two options you ask about are equivalent in the sense that they accept the same class of languages.
Indeed we said in class the stack does not have to be empty, all the input should be read (we added a special sign, $, to help identify this), and the machine should reach a final "accept" state. And of course,
as Jonathan suggested, proving equivalence is not a bad idea.