PlanetMath: context-free language

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

context-free language

(Definition)

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 have the form

$\displaystyle X\to w,$

where $X\in N$ and $w\in \Sigma^*$ . A context-free language is the formal language

generated by a context-free grammar

. In other words,

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

where $T:=\Sigma-N$ is the set of terminals, and $\sigma\stackrel{*}{\to}v$ simply means that the productions in

are applied a finite number of times to the starting symbol $\sigma$ so that

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.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), \nonumber$
		$\displaystyle (D, \verb.0.), (D, \verb.1.), (D, \verb.2.), (D, \verb.3.), (D, \... ...), (D, \verb.5.), (D, \verb.6.), (D, \verb.7.), (D, \verb.8.), (D, \verb.9.) \}$	(1)

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 is a non-terminal and $\gamma$ is a string of terminals and non-terminals.

Remarks.

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).
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.
A context-free grammar is context-sensitive if none of its productions has the form $X\to \lambda$ , where $\lambda$ is the empty word.

Bibliography

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

"context-free language" is owned by CWoo. [ full author list (3) | owner history (2) ]

(view preamble)

Other names:

context-free grammar, Type-2 grammar

Also defines:

context-free

Keywords:

syntax, grammar, formal language, Chomsky

This object's parent.

Attachments:: regular language (Definition) by mps
Chomsky normal form (Definition) by rspuzio
Backus-Naur form (Definition) by CWoo

Log in to rate this entry.
(view current ratings)

Cross-references: empty word, context-sensitive, regular languages, subset, generate, generator, sentence, decide, acceptor, automaton, pushdown automaton, string, non-terminal, Chomsky hierarchy, literals, integer, syntax, operator precedence, operators, terms, expression, infix arithmetic, starting symbol, number, finite, terminals, generated by, formal language, productions, formal grammar, alphabet, language
There are 11 references to this entry.

This is version 25 of context-free language, born on 2002-02-23, modified 2008-07-19.
Object id is 2546, canonical name is ContextFreeLanguage.
Accessed 22302 times total.

Classification:

AMS MSC:	68Q45 (Computer science :: Theory of computing :: Formal languages and automata)
	68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)

Pending Errata and Addenda

None.[ View all 11 ]

Discussion

forum policy

Interact