3
$\begingroup$

Are there any resources on how to convert a non-deterministic PDA to a deterministic one, if a deterministic PDA actually exists? Or is there a step by step way on how to do this, kind of like going from an NFA to DFA?

Thanks

  • 0
    For the record, you can not haz cheezburger. Look for entries from Jan. 12, 2007, in case the page number is not quite right by the time you see this: http://icanhascheezburger.com/page/1966/2011-11-03

1 Answers 1

3

No. Not every nondeterministic PDA has an equivalent deterministic PDA. Even if you have a nondeterministic PDA that is guaranteed to have a deterministic equivalent, there is no mechanical procedure to find it.