patternMinor
Grammatical characterization of deterministic context-free languages
Viewed 0 times
freelanguagesgrammaticaldeterministiccontextcharacterization
Problem
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?
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?
Solution
Wikipedia actually gives you the model and points to [1] for reference: LR grammars are equivalent to DPDA.
- On the Translation of Languages from Left to Right by Donald Knuth (1965) [free download]
Context
StackExchange Computer Science Q#7031, answer score: 4
Revisions (0)
No revisions yet.