Context-free languages (CFLs) are generated by context-free grammars. The set of all context-free languages is identical to the set of languages accepted by pushdown automata, and the set of regular languages is a subset of context-free languages.

An inputed language is accepted by a computational model if it runs through the model and ends in an accepting final state. All regular languages are context-free languages, but not all context-free languages are regular. Most arithmetic expressions are generated by context-free grammars, and are therefore, context-free languages.

Context-free languages and context-free grammars have applications in computer science and linguistics such as natural language processing and computer language design.

Context Free Languages Definition

In formal language theory, a language is defined as a set of strings of symbols that may be constrained by specific rules. Similarly, the written English language is made up of groups of letters (words) separated by spaces. A valid (accepted) sentence in the language must follow particular rules, the grammar.

A context-free language is a language generated by a context-free grammar. They are more general (and include) regular languages. The same context-free language might be generated by multiple context-free grammars.

The set of all context-free languages is identical to the set of languages that are accepted by pushdown  automata (PDA).

Here is an example of a language that is not regular (proof here) but is context-free:

{ aⁿbⁿ | n ≥ 0}.  This is the language of all strings that have an equal number of a’s and b’s.

In this notation,a⁴b⁴ can be expanded out too aaaabbbb, where there are four a’s and then four b’s. (So this isn’t exponentiation, through the notation is similar).

Read Also: Context Free Grammars

Closure Properties

Context-free languages have the following closure properties. A set is closed under an operation if doing the operation on a given set always produces a member of the same set. This means that if one of these closed operations is applied to a context-free language the result will also be a context-free language.

• Union: Context-free languages are closed under the union operation. This means that if  are both context-free languages, then  is also a context-free language.

Proof:

Here is a proof that context-free grammars are closed under union

1. Let L and P be generated by the context-free grammars, GL = (VL, ΣL, RL, SL) and GP = (VP, ΣP, RP, SP), respectively.

2. Without loss of generality, subscript each nonterminal symbol in GL with an L, and each nonterminal of GP with a P such that VL ∩ VP = ∅.

3. Define the CFG, G, that generates L ∪ P as follows: G=(VL ∪ VP ∪ {S}, ΣL ∪ ΣP, RL ∪ RP ∪ {S -> SL|SP}, S).

• Concatenation: If L and P are both context-free languages, then LP is also context free. The concatenation of a string is defined as follows: S₁S₂ = vw: v ∈ S₁ and w ∈ S₂.

Proof:

Here is a proof that context-free grammars are closed under union

1. 1. Let L and P be generated by the context-free grammars, GL = (VL, ΣL, RL, SL) and GP = (VP, ΣP, RP, SP), respectively.

   2. Without loss of generality, subscript each nonterminal symbol in GL with an L, and each nonterminal of GP with a P such that VL ∩ VP = ∅.

   3. Define the CFG, G, that generates L ∪ P as follows: G=(VL ∪ VP ∪ {S}, ΣL ∪ ΣP, RL ∪ RP ∪ {S -> SLSP}, S).

Every word that G generates is a word L followed by a word P, which is the definition of concatenation.

•  Kleene Star: If L  is a context-free language, then L ∗  is also context free. The Kleene star can repeat the string or symbol it is attached to any number of times (including zero times). The Kleene star basically performs a recursive concatenation of a string with itself. For example, {a,b}∗ = {ε, a, b, ab, aab, aaab, abb, ….} and so on. We’ve already proved that CFLs are closed under concatenation.

Context-free languages are not closed under complement or intersection.

If CFL’s  were closed under intersection then there would be CFLs that violate the pumping lemma for context-free languages which cannot be.

Please wait for our next post on Pumping Lemma.

Please Like Our Post on Facebook

Also see: Definition of Pushdown Automata