In
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
, deterministic context-free languages (DCFL) are a
proper subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of
context-free language
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
s. They are the context-free languages that can be accepted by a
deterministic pushdown automaton In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.
...
. DCFLs are always unambiguous, meaning that they admit an
unambiguous grammar
In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string ...
. 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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, 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 In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.
...
(DPDA). It is where the language power of
pushdown automata
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is
a type of automaton that employs a stack.
Pushdown automata are used in theories about what can be computed by machines. They are more capab ...
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.
Unambiguous grammar
In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string ...
s do not always generate a DCFL. For example, the language of even-length
palindrome
A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards, such as the words ''madam'' or ''racecar'', the date and time ''11/11/11 11:11,'' and the sentence: "A man, a plan, a canal – Panam ...
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.
Properties
Deterministic context-free languages can be recognized by a
deterministic Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
in polynomial time and
O(log
2 ''n'') space; as a corollary, DCFL is a subset of the complexity class
SC.
The set of deterministic context-free languages is closed under the following operations:
*
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
*
inverse homomorphism
*
right quotient In mathematics and computer science, the right quotient (or simply quotient) of a language L_1 with respect to language L_2 is the language consisting of strings ''w'' such that ''wx'' is in L_1 for some string ''x'' in Formally:
L_1 / L_2 = \
In ...
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:
*
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
*
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
*
concatenation
In formal language, formal language theory and computer programming, string concatenation is the operation of joining character string (computer science), character strings wikt:end-to-end, end-to-end. For example, the concatenation of "sno ...
*
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid c ...
*
ε-free morphism
*
Mirror image
A mirror image (in a plane mirror) is a reflected duplication of an object that appears almost identical, but is reversed in the direction perpendicular to the mirror surface. As an optical effect it results from reflection off from substances ...
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(
2.378) time, where is the length of the string. On the other hand, deterministic context-free languages can be accepted in O() time by an
LR() parser.
This is very important for
computer language
A computer language is a formal language used to communicate with a computer. Types of computer languages include:
* Construction language – all forms of communication by which a human can specify an executable problem solution to a compu ...
translation because many computer languages belong to this class of languages.
See also
*
Context free language
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
*
Deterministic pushdown automaton In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.
...
*
Deterministic context-free grammar In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the ...
*
Simple deterministic language
References
{{Formal languages and grammars
Formal languages