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:

    “A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
    —Ralph Waldo Emerson (1803–1882)