Context-free language

From Free net encyclopedia

A context-free language is a formal language that is accepted by some pushdown automaton. Context-free languages can be generated by context-free grammars.

Examples

An archetypical context-free language is <math>L = \{a^nb^n:n\geq1\}</math>, the language of all non-empty even-length strings, the entire first halves of which are <math>a</math>'s, and the entire second halves of which are <math>b</math>'s. <math>L</math> is generated by the grammar <math>S\to aSb ~|~ ab</math>, and is accepted by the pushdown automaton <math>M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\})</math> where <math>\delta</math> is defined as follows:

Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar <math>S\to SS ~|~ (S) ~|~ \lambda</math>. Also, most arithmetic expressions are generated by context-free grammars.

Closure Properties

Context-Free Languages are closed under the following operations. That is, if "L" and "P" are Context-Free Languages and "D" is a Regular Language, the following languages are Context-Free as well:

• the Kleene star L^* of L
• the homomorphism φ(L) of "L"
• the concatenation LP of L and P
• the union L∪P of "L" and "P"
• the intersection (with a Regular Language) L∩D of "L" and "D"

Context-Free Languages are not closed under complement, intersection, or difference.

See also

There is a pumping lemma for context-free languages, that gives a necessary condition for a language to be context-free.

References

• Template:Cite book Chapter 2: Context-Free Languages, pp.91–122.

Template:Formal languages and grammarscs:Bezkontextový jazyk de:Kontextfreie Sprache it:Linguaggio context-free he:שפה חופשית הקשר pl:Język bezkontekstowy ro:Limbaje independente de context fi:Yhteydetön kieli