Undecidable Problems
Some questions that are undecidable for wider classes of grammars become decidable for context-free grammars; e.g. the emptiness problem (whether the grammar generates any terminal strings at all), is undecidable for context-sensitive grammars, but decidable for context-free grammars.
Still, many problems remain undecidable. Examples:
Read more about this topic: Context-free Grammar
Famous quotes containing the word problems:
“Our young people are diseased with the theological problems of original sin, origin of evil, predestination, and the like. These never presented a practical difficulty to any man,—never darkened across any man’s road, who did not go out of his way to seek them. These are the soul’s mumps, and measles, and whooping- coughs, and those who have not caught them cannot describe their health or prescribe a cure. A simple mind will not know these enemies.”
—Ralph Waldo Emerson (1803–1882)