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 called DCFL[2] and 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. [3]
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(n3) time, whereas membership in a deterministic context-free language can be tested in O(n) time[4], where n is the length of the string.
In an early result of computational complexity theory, Steven Cook showed in 1979 that deterministic context-free languages can be recognized by a deterministic Turing machine in polynomial time and O(log2n) space; as a corollary, DCFL is contained in SC.[5]
References
- ^ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 233.
- ^ Complexity Zoo: Class DCFL
- ^ Hopcroft, John; Rajeev Motwani & Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253.
- ^ Harrison, Michael A. (1978). Introduction to Formal Language Theory. Addison-Wesley. p. 135.
- ^ S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.
| 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 | n/a | Star-free | Aperiodic finite |
| Each category of languages or grammars is a proper subset of the category directly above it. Any automaton in each category has an equivalent automaton in the category directly above it. |
|||
 |
This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
