Skip to main content
edited title
Link
Zephyr
  • 993
  • 3
  • 16
  • 34

PDA prefix property Working of NPDA

edited tags; edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
Zephyr
  • 993
  • 3
  • 16
  • 34

PDA prefix property

I read that acceptance of languages by DPDA using empty stack is a subset of languages accepted by DPDA using final state because of prefix property. I understood this statement by taking an example of regular language a*. Here if we use stack then we can't decide when to pop the symbols from stack. If we pop all the symbols(prefix belonging to language) then stack will become empty and we can't process the input further(left over input). So we can't accept a* using dpda by stack.

I read another statement that NPDA using stack can accept all languages which NPDA using final state will accept. Here we can have many copies of machine running simultaneously and we can non deterministically check if the input is accepted or not. But what if prefix like aa of input aaaaa is accepted by one of the machine ? Will all the machines stop and say yes (that is we can't proceed with the input further) or will some of the machines still continue with the remaining input even if one of them halts?