Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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]
share|cite|improve this answer
You are right! Of course, and I will again read that paper. I recall however that direct charecterization I was hinting at in the question, and which uses equvalence on non-terminals. I hope that someone will recognize what I mean, so I will not now formally accept the answer. (sorry) – Hendrik Jan Nov 30 '12 at 17:09
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?) – Hendrik Jan 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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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