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:
“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)
“I am not sure that it is of the first importance that you should be happy. Many an unhappy man has been of deep service to himself and to the world.”
—Woodrow Wilson (1856–1924)
“Kitsch is the daily art of our time, as the vase or the hymn was for earlier generations. For the sensibility it has that arbitrariness and importance which works take on when they are no longer noticeable elements of the environment. In America kitsch is Nature. The Rocky Mountains have resembled fake art for a century.”
—Harold Rosenberg (1906–1978)