Deterministic context-free language

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 is 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(n^2.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.

The deterministic context-free languages are exactly those recognized by some LR grammar^[5].

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² n) space; as a corollary, DCFL is a subset of the complexity class SC.^[6]

Properties

• DCFLs are not closed under Union.
• DCFLs are closed under Complementation.

See also

• Visibly pushdown languages
• Greibach's theorem proves that it is undecidable whether a given context-free language is deterministic

References

1. ^ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 233. 
2. ^ Complexity Zoo: Class DCFL
3. ^ Hopcroft, John; Rajeev Motwani & Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253. 
4. ^ Harrison, Michael A. (1978). Introduction to Formal Language Theory. Addison-Wesley. p. 135. 
5. ^ Hopcroft, John; Rajeev Motwani & Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. 
6. ^ 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.v · Categories: Formal languages Theoretical computer science stubs Wikimedia Foundation. 2010. Игры ⚽ Нужен реферат? Rocco Forte Akiha Tohno Look at other dictionaries: Deterministic context-free grammar — In formal grammar theory, the deterministic context free grammars (DCFGs) are a proper subset of the context free grammars. The deterministic context free grammars are those a deterministic pushdown automaton can recognize. A DCFG is the finite… …   Wikipedia 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. Contents 1 Examples 2 Closure… …   Wikipedia Context free — may refer to: Concepts context free grammar deterministic context free grammar stochastic context free grammar weighted context free grammar context free language Software Context Free, a computer language for context free grammars …   Wikipedia Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia Context-sensitive language — In theoretical computer science, a context sensitive language is a formal language that can be defined by a context sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used,… …   Wikipedia Mildly context-sensitive language — In formal grammar theory, mildly context sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced …   Wikipedia 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. A deterministic… …   Wikipedia Stochastic context-free grammar — A stochastic context free grammar (SCFG; also probabilistic context free grammar, PCFG) is a context free grammar in which each production is augmented with a probability. The probability of a derivation (parse) is then the product of the… …   Wikipedia Deterministic finite-state machine — An example of a Deterministic Finite Automaton that accepts only binary numbers that are multiples of 3. The state S0 is both the start state and an accept state. In the theory of computation and automata theory, a deterministic finite state… …   Wikipedia Context-sensitive grammar — A context sensitive grammar (CSG) is a formal grammar in which the left hand sides and right hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context sensitive grammars are more general than… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”