Jon Bergmeier: EPDA is undecidable.Let T be a Turing Machine that decides EQcfg.T = "On input where M1, M2 is a PDA"1. Run EPDA on input M1, M22. If EPDA accepts, then accept, otherwise reject.Since EQcfg is undecidable, it follows that EPDA is also undecidable by a reduction argument....Show more
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment