3
$\begingroup$

I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the internet.

Clarification: I don't care about deciding if the language is deterministic, just whether a specific grammar is deterministic.

$\endgroup$
1
  • 2
    $\begingroup$ Yes it is decidable, a sketch of the proof can be found in this lecture: Deterministic Context-Free Languages; they start establishing the equivalence between DCFGs and endmarked languages; then costruct a special DFA DK to identify "handles" and determine whether the grammar is deterministic by examining DK's accept states. $\endgroup$ – Marzio De Biasi Oct 13 '20 at 7:03

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.