Deterministic context-free language
Encyclopedia
A deterministic context-free language is a formal language
which is defined by a deterministic context-free grammar
. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton
.
The set of deterministic context-free languages is a proper subset of the set of context-free language
s that possess an unambiguous context free grammar. For example, the language of even-length palindrome
s 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.
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, where n is the length of the string.
The deterministic context-free languages are exactly those recognized by some LR grammar.
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
.
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
which is defined by a deterministic context-free grammar
Deterministic context-free grammar
In formal grammar theory, the deterministic context-free grammars are a proper subset of the context-free grammars. The deterministic context-free grammars are those a deterministic pushdown automaton can recognize...
. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton
Deterministic pushdown automaton
In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack....
.
The set of deterministic context-free languages is a proper subset of the set of context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s that possess an unambiguous context free grammar. For example, the language of even-length palindrome
Palindrome
A palindrome is a word, phrase, number, or other sequence of units that can be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers....
s 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.
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, where n is the length of the string.
The deterministic context-free languages are exactly those recognized by some LR grammar.
In an early result of computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, Stephen Cook
Stephen Cook
Stephen Arthur Cook is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity...
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
SC (complexity)
In computational complexity theory, SC is the complexity class of problems solvable by a deterministic Turing machine in polynomial time and polylogarithmic space...
.
See also
- Visibly pushdown languages
- Greibach's theorem proves that it is undecidable whether a given context-free language is deterministic