Importance
The languages of this class have great practical importance in computer science as they can be parsed much more efficienly 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 a LR(k) parser. This is very important for computer language translation because many computer languages belong to this class of languages.
Read more about this topic: Deterministic Context-free Language
Famous quotes containing the word importance:
“The child thinks of growing old as an almost obscene calamity, which for some mysterious reason will never happen to itself. All who have passed the age of thirty are joyless grotesques, endlessly fussing about things of no importance and staying alive without, so far as the child can see, having anything to live for. Only child life is real life.”
—George Orwell (1903–1950)
“Society is the stage on which manners are shown; novels are the literature. Novels are the journal or record of manners; and the new importance of these books derives from the fact, that the novelist begins to penetrate the surface, and treat this part of life more worthily.”
—Ralph Waldo Emerson (1803–1882)
“The Mississippi, the Ganges, and the Nile,... the Rocky Mountains, the Himmaleh, and Mountains of the Moon, have a kind of personal importance in the annals of the world.”
—Henry David Thoreau (1817–1862)