Decidability Properties
The following problems are undecidable for arbitrary context-free grammars A and B:
- Equivalence: is ?
- is ? (However, the intersection of a context-free language and a regular language is context-free, so if were a regular language, this problem becomes decidable.)
- is ?
- is ?
The following problems are decidable for arbitrary context-free languages:
- is ?
- is finite?
- Membership: given any word, does ? (membership problem is even polynomially decidable - see CYK algorithm and Earley's Algorithm)
Read more about this topic: Context-free Language
Famous quotes containing the word properties:
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)