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(log 2 n) space as a corollary, DCFL is a subset of the complexity class SC. The deterministic context-free languages are exactly those recognized by some LR grammar. The best known algorithm to test membership in any context-free language is Valiant's algorithm, taking O( n 2.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. In the naive implementation, it must make copies of the stack every time a nondeterministic step occurs.
![context free language programs context free language programs](https://media.geeksforgeeks.org/wp-content/uploads/grammertree.jpg)
The complexity of the program and execution of a deterministic pushdown automaton is vastly less than that of a nondeterministic one. The languages of this class have practical importance in computer science. 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.
![context free language programs context free language programs](https://2.bp.blogspot.com/-C1mUc1rjaS0/XK27UNS7tPI/AAAAAAAAN_I/zsCMWn5r1Qk70JDe-x9o-qyeM2T7lU-_QCEwYBhgL/w1200-h630-p-k-no-nu/Chapter08.jpg)
The set of deterministic context-free languages is a proper subset of the set of context-free languages that possess an unambiguous context free grammar.
![context free language programs context free language programs](http://image3.slideserve.com/6778019/non-context-free-languages-n.jpg)
The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton. A deterministic context-free language is a formal language which is defined by a deterministic context-free grammar.