Site icon

Context Free Languages

Context Free Languages

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.

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 LP as follows: G=(VL ∪ VP ∪ {S}, ΣL ∪ ΣP, RL ∪ RP ∪ {S -> SL|SP}, S).
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 LP 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.

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

Exit mobile version