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:
“A toothache, or a violent passion, is not necessarily diminished by our knowledge of its causes, its character, its importance or insignificance.”
—T.S. (Thomas Stearns)
“Coming together again after a long day apart can be an experience where joy, relief, anger, and fatigue are all present in different degrees both for the parent and for the child. Because of their importance in marking the resumption of direct contact, reunions deserve as much attention and care as separations to enhance the relationship between parent and child.”
—Alicia F. Lieberman (20th century)
“There is much to be said in favour of modern journalism. By giving us the opinions of the uneducated, it keeps us in touch with the ignorance of the community. By carefully chronicling the current events of contemporary life, it shows us of what very little importance such events really are. By invariably discussing the unnecessary, it makes us understand what things are requisite for culture, and what are not.”
—Oscar Wilde (1854–1900)