Deterministic context-free languages are commonly defined using an automaton concept, the (restricted, deterministic) pushdown automaton. To some that is confusing, as the name context-free refers to a grammar type.

I seem to remember there exists a characterization of the DCF languages using grammars. In my recollection it used a complicated equivalence on non-terminals. Can anyone provide a pointer to that work?


Wikipedia actually gives you the model and points to [1] for reference: LR grammars are equivalent to DPDA.

  1. On the Translation of Languages from Left to Right by Donald Knuth (1965) [free download]
  • $\begingroup$ Thanks. This helped me to re-investigate. The class I was looking for is called strict deterministic grammars (Harrison & Havel, JCSS 1973) and characterizes the prefix-free deterministic context-free languages. Not all of them. The good side if the class is that is defined on the productions, not on the derivations, like LR-grammars do. Adding an end-marker mekes every language prefix-free, so in practical terms that is not a big loss. Note wikipedia has the notion, hidden under "Strict determinism". (Can I do links in a comment?) $\endgroup$ Nov 30 '12 at 21:02

Just an additional note of possible use: the PLL(0) grammars == the strict deterministic grammars, perhaps an easier approach for both understanding and practical application. A nice description is in Parsing Techniques, 2nd Edition, pp354-357.

  • 2
    $\begingroup$ Who would the author(s) of the cited book be? $\endgroup$
    – vonbrand
    Feb 25 '13 at 1:02
  • $\begingroup$ @vonbrand Grune/Jacobs Alas, the previous edition (free online) does not cover this topic and there's no Google Books preview AFAICT. $\endgroup$
    – Ron Burk
    Feb 25 '13 at 7:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.