Deterministic Context-free Language Information
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 even-length 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 is Valiant's algorithm, taking O(n2.378) 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, Stephen Cook showed in 1979 that deterministic context-free languages can be recognized by a deterministic Turing machine in polynomial time and O(log2 n) space; as a corollary, DCFL is a subset of the complexity class SC.[5]
See also
- Visibly pushdown languages
- Greibach's theorem proves that it is undecidable whether a given context-free language is deterministic
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.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| P ≟ NP | This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it. · · |
Categories: Formal languages |
|