Properties of Context-free Languages
- The reverse of a context-free language is context-free, but the complement need not be.
- Every regular language is context-free because it can be described by a context-free grammar.
- The intersection of a context-free language and a regular language is always context-free.
- There exist context-sensitive languages which are not context-free.
- To prove that a given language is not context-free, one may employ the pumping lemma for context-free languages or a number of other methods, such as Ogden's lemma, Parikh's theorem, or using closure properties.
- Context Free Languages are closed under Union, Concatenation, and Kleene star.
Read more about this topic: Context-free Language
Famous quotes containing the words properties of, properties and/or languages:
“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)
“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)
“I am always sorry when any language is lost, because languages are the pedigree of nations.”
—Samuel Johnson (1709–1784)