Wikia

Language: Linguistics · Semiotics · Speech

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.

ExamplesEdit

An archetypical context-free language is $L = \{a^nb^n:n\geq1\}$ , 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\}, \{a,b,z\}, \delta, q_0, \{q_f\})$ where $\delta$ is defined as follows:

$\delta(q_0, a, z) = (q_0, a)$
$\delta(q_0, b, ax) = (q_1, x)$
$\delta(q_1, b, ax) = (q_1, x)$
$\delta(q_1, b, bz) = (q_f, z)$

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) ~|~ \lambda$ . Also, most arithmetic expressions are generated by context-free grammars.

Closure Properties Edit

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.

References Edit

Michael Sipser (1997). Introduction to the Theory of Computation, PWS Publishing. ISBN 0-534-94728-X. Chapter 2: Context-Free Languages, pp.91–122.

Automata theory: formal languages and formal grammars
Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
Type-2	Context-free	Context-free	Pushdown
Type-3	Regular	Regular	Finite
Each category of languages or grammars is a proper superset of the category directly beneath it.

cs:Bezkontextový jazyk

de:Kontextfreie Sprache he:שפה חופשית הקשר ro:Limbaje independente de context fi:Yhteydetön kieli

This page uses Creative Commons Licensed content from Wikipedia (view authors).

Wikia

Context free language

Contents

ExamplesEdit

Closure Properties Edit

See alsoEdit

References Edit

Photos

Recent Wiki Activity