Context-free language

Template:One source In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). Different CF grammars can generate the same CF language, or conversely, a given CF language can be generated by different CF grammars. It is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties).

The set of all context-free languages is identical to the set of languages accepted by pushdown automata, which makes these languages amenable to parsing. Indeed, given a CFG, there is a direct way to produce a pushdown automaton for the grammar (and corresponding language), though going the other way (producing a grammar given an automaton) is not as direct.

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

Examples

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

$\delta (q_0,a,z)=(q_0,az)$
$\delta (q_0,a,a)=(q_0,aa)$
$\delta (q_0,b,a)=(q_1,\epsilon )$
$\delta (q_1,b,a)=(q_1,\epsilon )$

$\delta ({\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}}_1,\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d},\mathrm{p}\mathrm{o}\mathrm{p})=({\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}}_2,\mathrm{p}\mathrm{u}\mathrm{s}\mathrm{h})$

Unambiguous CFLs are a proper subset of all CFLs: there are inherently ambiguous CFLs. An example of an inherently ambiguous CFL is the union of $\{a^n{b}^m{c}^m{d}^n|n,m>0\}$ with $\{a^n{b}^n{c}^m{d}^m|n,m>0\}$. This set is context-free, since the union of two context-free languages is always context-free. But there is no way to unambiguously parse strings in the (non-context-free) subset $\{a^n{b}^n{c}^n{d}^n|n>0\}$ which is the intersection of these two languages.Template:Sfn

Languages that are not context-free

The set $\{a^n{b}^n{c}^n{d}^n|n>0\}$ is a context-sensitive language, but there does not exist a context-free grammar generating this language.Template:Sfn So 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 or Parikh's theorem.

Closure properties

Context-free languages are closed under the following operations. That is, if L and P are context-free languages, the following languages are context-free as well:

• the union $L\cup P$ of L and P
• the reversal of L
• the concatenation $L\cdot P$ of L and P
• the Kleene star $L^{*}$ of L
• the image $\phi (L)$ of L under a homomorphism $\phi$
• the image ${\phi }^{-1}(L)$ of L under an inverse homomorphism ${\phi }^{-1}$
• the cyclic shift of L (the language $\{vu:uv\in L\}$)

Context-free languages are not closed under complement, intersection, or difference. However, if L is a context-free language and D is a regular language then both their intersection $L\cap D$ and their difference $L\setminus D$ are context-free languages.

Nonclosure under intersection and complement

The context-free languages are not closed under intersection. This can be seen by taking the languages $A=\{a^n{b}^n{c}^m\mid m,n\ge 0\}$ and $B=\{a^m{b}^n{c}^n\mid m,n\ge 0\}$, which are both context-free. Their intersection is $A\cap B=\{a^n{b}^n{c}^n\mid n\ge 0\}$, which can be shown to be non-context-free by the pumping lemma for context-free languages.

Context-free languages are also not closed under complementation, as for any languages A and B: $A\cap B=\overline{\stackrel{‾}{A}\cup \stackrel{‾}{B}}$.

Decidability properties

The following problems are undecidable for arbitrary context-free grammars A and B:

• Equivalence: Given two context-free grammars A and B, is $L(A)=L(B)$?
• Intersection Emptiness: Given two context-free grammars A and B, is $L(A)\cap L(B)=\mathrm{\varnothing }$ ? However, the intersection of a context-free language and a regular language is context-free, and the variant of the problem where B is a regular grammar is decidable.
• Containment: Given a context-free grammar A, is $L(A)\subseteq L(B)$ ? Again, the variant of the problem where B is a regular grammar is decidable.
• Universality: Given a context-free grammar A, is $L(A)={\mathrm{\Sigma }}^{*}$ ?

The following problems are decidable for arbitrary context-free languages:

• Emptiness: Given a context-free grammar A, is $L(A)=\mathrm{\varnothing }$ ?
• Finiteness: Given a context-free grammar A, is $L(A)$ finite?
• Membership: Given a context-free grammar G, and a word $w$, does $w\in L(G)$ ? Efficient polynomial-time algorithms for the membership problem are the CYK algorithm and Earley's Algorithm.

Parsing

Determining an instance of the membership problem; i.e. given a string $w$, determine whether $w\in L(G)$ where $L$ is the language generated by some grammar $G$; is also known as parsing.

Formally, the set of all context-free languages is identical to the set of languages accepted by pushdown automata (PDA). Parser algorithms for context-free languages include the CYK algorithm and the Earley's Algorithm.

A special subclass of context-free languages are the deterministic context-free languages which are defined as the set of languages accepted by a deterministic pushdown automaton and can be parsed by a LR(k) parser.

See also parsing expression grammar as an alternative approach to grammar and parser.

See also

• Deterministic context-free language
• Parsing

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

References

• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 Chapter 2: Context-Free Languages, pp. 91–122.
• Jean-Michel Autebert, Jean Berstel, Luc Boasson, Context-Free Languages and Push-Down Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111-174.

Other Sports Official Alfonzo from Chase, has hobbies and interests for instance fast, property developers in new industrial launch singapore and aquariums. In recent times has visited Monasteries of Haghpat and Sanahin.