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:
{ anbn | n ≥ 0}. This is the language of all strings that have an equal number of a’s and b’s.
In this notation,a4b4 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
-
Let L and P be generated by the context-free grammars, GL = (VL, ΣL, RL, SL) and GP = (VP, ΣP, RP, SP), respectively.
-
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 = ∅.
-
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: S1S2 = vw: v ∈ S1 and w ∈ S2.
Proof: Here is a proof that context-free grammars are closed under union
-
-
Let L and P be generated by the context-free grammars, GL = (VL, ΣL, RL, SL) and GP = (VP, ΣP, RP, SP), respectively.
-
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 = ∅.
-
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