In formal language theory, deterministic contextfree languages (DCFL) are a proper subset of contextfree languages. They are the contextfree languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar, but any (nonempty) DCFLs also admits ambiguous grammars. There are nondeterministic 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.
Contents

Description 1

Properties 2

Importance 3

See also 4

References 5
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 contextfree languages.^{[1]} Unambiguous grammars do not always generate a DCFL. For example, the language of evenlength palindromes on the alphabet of 0 and 1 has the unambiguous contextfree 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 semiparsed string. ^{[2]}
Properties
Deterministic contextfree 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.^{[3]} The set of deterministic contextfree 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 contextfree 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 contextfree language is Valiant's algorithm, taking O(n^{2.378}) time, where n is the length of the string. On the other hand, deterministic contextfree languages can be accepted in O(n) time by a LR(k) parser.^{[4]} This is very important for computer language translation because many computer languages belong to this class of languages.
See also
References

^

^

^ 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.

^




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.


This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.