# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Context-free language

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 $L = \{a^nb^n:n\geq1\}$, the language of all even-lengths 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 = ({q0,q1,qf},{a},{a,b,z},δ,q0,{qf}) where δ is defined as follows:

δ(q0,a,z) = (q0,a)
δ(q0,b,ax) = (q1,x)
δ(q1,b,ax) = (q1,x)
δ(q1,b,bz) = (qf,z)

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

## Closure properties

The family of context-free languages is closed under concatenation and union but not intersection or difference. It is, however, closed under difference with a regular language.