What does it mean to say a language is context-free?

What does it mean to say a language is context-free?

A context-free grammar is defined as a grammar in which every production rule is of the form $A \rightarrow \alpha$, where $A$ is a variable and $\alpha$ is a sequence of variables and terminals.

Formally, a context-free grammar can be defined as a 4-tuple $(V, \Sigma, R, S)$, where $V$ is a finite set consisting of the variables, $\Sigma$ is a finite set consisting of the terminals, $R$ is a set of production rules (in the form mentioned above), and $S \in V$ is the starting variable.

The language of a context-free grammar is the set of strings that can be derived from its start variable. A context-free language is any language that is generated by a context-free grammar.

For example, $\{ 0^n1^n : n \ge 0 \}$ is context-free because it is generated by the context-free grammar $(\{S\}, \{0, 1\}, R, S)$, where the set of rules, $R$, is $$S \rightarrow 0S1 \mid \varepsilon.$$

(Note: I am using $\varepsilon$ to denote the empty or null string.)

As seen in this example, the set of context-free languages contains languages that are not regular. Also, since it is easy to mimic a DFA with a context-free grammar, the set of regular languages is a proper subset of the set of context-free languages. Pushdown automata are the automata cousins of context-free grammars; they accept context-free languages and there exist algorithms to convert between the two models.

Note that the language $\{ a^nb^nc^n : n \ge 0 \}$ is not context-free (try to write a context-free grammar to generate this language and you will get a feeling for why). It can be proven that the language is not context-free with the pumping-lemma for context-free languages, which I will leave as an exercise for the reader.

There are more powerful grammars, such as context-sensitive grammars, which allow the production rules to have the form $\beta A \gamma \rightarrow \beta\alpha\gamma$, where $\alpha$, $\beta$, and $\gamma$ are sequences of variables and terminals. Context-sensitive grammars are as powerful as linear bounded automata (LBA).

Given the technical definition of what a language is and what context-free is, it means that in the processing of rules defining the language, no context is used. That is, any variable is rewritten by itself, with no context. Once a variable is produced in a derivation, none of the string around that variable will ever be involved in any further derivation...no context is used in rewriting a variable.

More complicated languages do not have this restriction (they may allow use of context/other adjacent variables and terminals in rewriting a variable).

Context-free languages are "easier" to parse (quicker/more efficiently) than context sensitive ones.

Note that the term 'context' is very technical here; it is referring to the context of a substring when rewriting. Technical terms have a life of their own and don't necessarily relate well to the first layman's understanding of the word.

Another characterisation is this: The set of context-free languages CFL is the set of all languages that are accepted by (maybe nondeterministic) push-down automata (finite automata plus one stack).

More intuitively, context-free languages have the property that different parts of a word are independent in a certain sense, namely in the same way as dynamic programming optimises subproblems independently. Not conincidentally, context-free grammars can by parsed by dynamic programming (CYK algorithm), non-context-free can not (in general).