## You are here

Homecontext-free language

## Primary tabs

# context-free language

A *context-free language* is a language over some alphabet that can be generated from a particular kind of a grammar known as a *context-free grammar*.

Formally, a *context-free grammar* is a formal grammar $G=(\Sigma,N,P,\sigma)$ whose productions in $P$ have the form

$X\to w,$ |

where $X\in N$ and $w\in\Sigma^{*}$. A *context-free language* is the formal language $L(G)$ generated by a context-free grammar $G$. In other words,

$L(G):=\{v\in T^{*}\mid\sigma\stackrel{*}{\to}v\},$ |

where $T:=\Sigma-N$ is the set of terminals, and $\sigma\stackrel{*}{\to}v$ simply means that the productions in $P$ are applied a finite number of times to the starting symbol $\sigma$ so that $v$ is reached in the end.

This formal definition is not initially very enlightening. As an example, consider typical infix arithmetic notation. An expression typically consists of one or more terms, joined together by operators with varying precedence.
Parentheses can be used to override operator precedence. This syntax is a context-free language. Let us describe such expressions with the operators `+`

and `-`

with lowest precedence, and `*`

and `/`

with highest precedence, where all operators are left-associative and the only other allowed symbols are integer literals and parentheses.

$\displaystyle T$ | $\displaystyle:=$ | $\displaystyle\left\{\verb.0.,\verb.1.,\verb.2.,\verb.3.,\verb.4.,\verb.5.,% \verb.6.,\verb.7.,\verb.8.,\verb.9.,\verb.(.,\verb.).,\verb.+.,\verb.-.,\verb.% *.,\verb./.\right\}$ | ||

$\displaystyle N$ | $\displaystyle:=$ | $\displaystyle\left\{S,A,B,C,D\right\}$ | ||

$\displaystyle P$ | $\displaystyle:=$ | $\displaystyle\{(S,A),(S,S\verb.+.A),(S,S\verb.-.A),$ | ||

$\displaystyle(A,B),(A,A\verb.*.B),(A,A\verb./.B),$ | ||||

$\displaystyle(B,C),(B,\verb.(.S\verb.).),(C,D),(C,CD),$ | ||||

$\displaystyle(D,\verb.0.),(D,\verb.1.),(D,\verb.2.),(D,\verb.3.),(D,\verb.4.),% (D,\verb.5.),(D,\verb.6.),(D,\verb.7.),(D,\verb.8.),(D,\verb.9.)\}$ | ||||

$\displaystyle\sigma$ | $\displaystyle:=$ | $\displaystyle S$ |

It can be shown that the languages of the classical propositional logic and predicate logic are both context-free.

Context-free grammars are also known as Type-2 grammars in the Chomsky hierarchy. The Chomsky hierarchy specifies Type-2 grammars as consisting only of production rules of the form $A\to\gamma$, where $A$ is a non-terminal and $\gamma$ is a string of terminals and non-terminals.

Remarks.

1. A context-free grammar can be represented by a pushdown automaton. The automaton serves both as an

*acceptor*for the language (that is, it can decide whether or not any arbitrary sentence is in the language) and as a*generator*for the language (that is, it can generate any finite sentence in the language in finite time).2. The syntaxes of most programming languages are context-free grammars (or very close to it). A very useful subset of context-free languages are regular languages.

3. A context-free grammar $G$ is context-sensitive if none of its productions has the form $X\to\lambda$, where $\lambda$ is the empty word.

4. The family of context-free languages has the following closure properties: union, concatenation, Kleene star, homomorphism, inverse homomorphism, reversal, and intersection with a regular language. However, it is not closed under intersection, set difference, and complementation.

# References

- 1 S. Ginsburg The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966).

## Mathematics Subject Classification

68Q45*no label found*68Q42

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Attached Articles

## Corrections

missing angle brackets in BNF by jac ✓

also defines by CWoo ✓

minor items by CWoo ✓

confusing sentence by ashkotin ✓

## Comments

## theorem about single-character language?

I can't find it anywhere - the proof for the theorem that a CFG over a single-character alphabet is regular... Can anyone help..?