| Revision as of 23:23, 6 February 2015 edit95.107.208.222 (talk) →Properties← Previous edit | Revision as of 01:14, 7 February 2015 edit undoBgwhite (talk | contribs)Extended confirmed users547,151 editsm fix borked tag using AWB (10813)Next edit → | ||
| Line 5: | Line 5: | ||
| ==Description== | ==Description== | ||
| The notion of the DCFL is closely related to the ] (DPDA). It is where the language power of a ] is reduced if we make it deterministic; the pushdown automaton becomes unable to choose between different state transition alternatives and as a consequence cannot recognize all context-free languages.<ref>{{cite book | last = ] | first = John |author2=] | title = ] | year = 1979 | publisher = Addison-Wesley | page = 233 }}</ref> ]s do not always generate a DCFL. For example, the language of even-length ]s on the alphabet of 0 and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string. |
The notion of the DCFL is closely related to the ] (DPDA). It is where the language power of a ] is reduced if we make it deterministic; the pushdown automaton becomes unable to choose between different state transition alternatives and as a consequence cannot recognize all context-free languages.<ref>{{cite book | last = ] | first = John |author2=] | title = ] | year = 1979 | publisher = Addison-Wesley | page = 233 }}</ref> ]s do not always generate a DCFL. For example, the language of even-length ]s on the alphabet of 0 and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.<ref>{{cite book | last = ] | first = John | coauthors = ] & ] | title = ] 2nd edition | year = 2001 | publisher = Addison-Wesley | pages = 249–253 }}</ref> | ||
| ==Properties== | ==Properties== | ||
| Deterministic context-free languages can be recognized by a ] in polynomial time and ](log<sub>2</ |
Deterministic context-free languages can be recognized by a ] in polynomial time and ](log<sub>2</sub> ''n'') space; as a corollary, '''DCFL''' is a subset of the complexity class ''']'''.<ref>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.</ref> The set of deterministic context-free languages is not closed under ] but is closed under ]. | ||
| ==Importance== | ==Importance== | ||
| The languages of this class have great practical importance in computer science as they can be parsed much more efficiently than nondeterministic context-free languages. The complexity of the program and execution time of a deterministic pushdown automaton is vastly less than that of a nondeterministic one. In the naive implementation, the latter 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 ], taking O(''n''<sup>2.378</sup>) time, where n is the length of the string. On the other hand, deterministic context-free languages can be accepted in O(''n'') time by a ].<ref>{{cite doi|10.1016/S0019-9958(65)90426-2}}</ref> This is very important for ] translation because many computer languages belong to this class of languages. | The languages of this class have great practical importance in computer science as they can be parsed much more efficiently than nondeterministic context-free languages. The complexity of the program and execution time of a deterministic pushdown automaton is vastly less than that of a nondeterministic one. In the naive implementation, the latter 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 ], taking O(''n''<sup>2.378</sup>) time, where n is the length of the string. On the other hand, deterministic context-free languages can be accepted in O(''n'') time by a ].<ref>{{cite doi|10.1016/S0019-9958(65)90426-2}}</ref> This is very important for ] translation because many computer languages belong to this class of languages. | ||
| ==See also== | ==See also== | ||
Revision as of 01:14, 7 February 2015
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar, but any (non-empty) DCFLs also admits ambiguous grammars. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs.
DCFLs are of great practical interest, as they can be parsed in linear time, and various restricted forms of DCFGs admit simple practical parsers. They are thus widely used throughout computer science.
Description
The notion of the DCFL is closely related to the deterministic pushdown automaton (DPDA). It is where the language power of a pushdown automaton is reduced if we make it deterministic; the pushdown automaton becomes unable to choose between different state transition alternatives and as a consequence cannot recognize all context-free languages. Unambiguous grammars do not always generate a DCFL. For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.
Properties
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. The set of deterministic context-free languages is not closed under union but is closed under complement.
Importance
The languages of this class have great practical importance in computer science as they can be parsed much more efficiently than nondeterministic context-free languages. The complexity of the program and execution time of a deterministic pushdown automaton is vastly less than that of a nondeterministic one. In the naive implementation, the latter 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) time, where n is the length of the string. On the other hand, deterministic context-free languages can be accepted in O(n) time by a LR(k) parser. This is very important for computer language translation because many computer languages belong to this class of languages.
See also
- Context free language
- Deterministic pushdown automaton
- Deterministic context-free grammar
- Simple deterministic language
References
- Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 233.
- Hopcroft, John (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253.
{{cite book}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - 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.
- Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/S0019-9958(65)90426-2, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1016/S0019-9958(65)90426-2instead.
| Automata theory: formal languages and formal grammars | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| |||||||||
| Each category of languages, except those marked by a , is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line. | |||||||||