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 awareness of the all-surpassing importance of social groups is now general property in America.”
—Johan Huizinga (1872–1945)
“Any novel of importance has a purpose. If only the “purpose” be large enough, and not at outs with the passional inspiration.”
—D.H. (David Herbert)
“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)