Deterministic context-free language
In
DCFLs are of great practical interest, as they can be parsed in
Description
The notion of the DCFL is closely related to the
Properties
Deterministic context-free languages can be recognized by a
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() is the subset of all strings having a proper prefix that also belongs to .
- min: min() is the subset of all strings that do not have a proper prefix in .
- max: max() is the subset of all strings that are not the prefix of a longer string in .
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(n2.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.
See also
- Context free language
- Deterministic pushdown automaton
- Deterministic context-free grammar
- Simple deterministic language
References
- Introduction to automata theory, languages, and computation. Addison-Wesley. p. 233.
- Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253.
- .
- ^ ISBN 978-3-642-53554-3.
- .