Or is it possible to construct more than one DPDA that accepts exactly the same language?

  • 2
    $\begingroup$ Exercise: Find a nontrivial language (e.g. one that isn't finite), and construct a DPDA for it. Now turn that DPDA into a DPDA with more states. $\endgroup$
    – Pseudonym
    Oct 19 '20 at 12:29
  • 1
    $\begingroup$ Another exercise: Construct an infinite number of DPDA for the empty language. $\endgroup$ Oct 19 '20 at 12:56
  • 1
    $\begingroup$ A better question would be: is there a unique minimal DPDA, just as there is a unique minimal DFA? $\endgroup$ Oct 19 '20 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.