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 transision 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 transisions to accommodate for the different possible lengths of a semi-parsed string.
Read more about this topic: Deterministic Context-free Language
Famous quotes containing the word description:
“An intentional object is given by a word or a phrase which gives a description under which.”
—Gertrude Elizabeth Margaret Anscombe (b. 1919)
“Do not require a description of the countries towards which you sail. The description does not describe them to you, and to- morrow you arrive there, and know them by inhabiting them.”
—Ralph Waldo Emerson (1803–1882)
“He hath achieved a maid
That paragons description and wild fame;
One that excels the quirks of blazoning pens.”
—William Shakespeare (1564–1616)