Deterministic context-free language

From Wikipedia, the free encyclopedia

A deterministic context-free language is a formal language which is defined by a deterministic context-free grammar.^[1] The set of deterministic context-free languages is identical to the set of languages accepted by a deterministic pushdown automaton.

The set of deterministic context-free languages are a proper subset of the set of context-free languages that possess an unambiguous context free grammar. For example, the language of palindromes on the alphabet of 0 and 1 has the simple, unambiguous grammar S → 0S0 | 1S1 | ε, but it cannot be parsed by a deterministic push down automaton. ^[2]

The languages of this class have practical importance in computer science. The complexity of the program and execution of a deterministic pushdown automaton is vastly less than that of a nondeterministic one. In the naive implementation, it must make copies of the stack every time a nondeterministic step occurs. The best known algorithm to test membership in any context-free language takes O(n³) time, whereas membership in a deterministic context-free language can be tested in O(n) time^{[citation needed]}, where n is the length of the string.

[edit] References

1. ^ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley, 233. 
2. ^ Hopcroft, John; Rajeev Motwani & Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley, 249–253. 

Automata theory: formal languages and formal grammars

Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
n/a	Tree-adjoining etc.	(Mildly context-sensitive)	Embedded pushdown
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
n/a		Star-free	Counter-Free
Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it.