Context-free Grammar - Undecidable Problems

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:

    An interesting play cannot in the nature of things mean anything but a play in which problems of conduct and character of personal importance to the audience are raised and suggestively discussed.
    George Bernard Shaw (1856–1950)