Deterministic context-free language

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

YouTube Encyclopedic

1/3
Views:
19 386
14 812
566 200

Transcription

Description

The notion of the DCFL is closely related to the deterministic pushdown automaton (DPDA). It is where the language power of pushdown automata is reduced to if we make them deterministic; the pushdown automata become unable to choose between different state-transition alternatives and as a consequence cannot recognize all context-free languages.^[1] 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.^[2]

Properties

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.^[3]

The set of deterministic context-free languages is closed under the following operations:^[4]

complement
inverse homomorphism
right quotient with a regular language
pre: pre( $L$ ) is the subset of all strings having a proper prefix that also belongs to $L$ .
min: min( $L$ ) is the subset of all strings that do not have a proper prefix in $L$ .
max: max( $L$ ) is the subset of all strings that are not the prefix of a longer string in $L$ .

The set of deterministic context-free language is not closed under the following operations:^[4]

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^2.378) 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 an LR(k) parser.^[5] This is very important for computer language translation because many computer languages belong to this class of languages.

References

^ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 233.
^ Hopcroft, John; Rajeev Motwani; Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253.
^ Cook, Stephen A. (April 30 – May 2, 1979). "Deterministic CFL's are accepted simultaneously in polynomial time and log squared space". Proceedings of the eleventh annual ACM Symposium on Theory of Computing - STOC '79. Atlanta. pp. 338–345. doi:10.1145/800135.804426.
^ ^a ^b Hoogeboom, Hendrik; Engelfriet, Joost (2004). Formal Languages and Applications. Springer-Verlag Berlin Heidelberg. p. 128. ISBN 978-3-642-53554-3.
^ Knuth, D. E. (July 1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.

Automata theory: formal languages and formal grammars

Chomsky hierarchy	Grammars	Languages	Abstract machines
Type-0 — Type-1 — — — — — Type-2 — — Type-3 — —	Unrestricted (no common name) Context-sensitive Positive range concatenation Indexed — Linear context-free rewriting systems Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular — Non-recursive	Recursively enumerable Decidable Context-sensitive Positive range concatenation^* Indexed^* — Linear context-free rewriting language Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular Star-free Finite	Turing machine Decider Linear-bounded PTIME Turing Machine Nested stack Thread automaton restricted Tree stack automaton Embedded pushdown Nondeterministic pushdown Deterministic pushdown Visibly pushdown Finite Counter-free (with aperiodic finite monoid) Acyclic finite

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 page was last edited on 29 October 2022, at 11:07

From Wikipedia, the free encyclopedia