Context-free Language - Decidability Properties

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)