CFG Properties and Applications

  • Post author:
Download PDF

CFG Properties and Applications

CFG- Context-free grammar is closure under:

  1. Union
  2. Concatenation
  3. Kleene Star Operation


Let suppose L1 and L2 are languages, they must have the finite set of alphabet and their grammar have to be drawn.

L1 ∪ L2 has to be context-free.


S → aS

S → φ

S → bS

S → φ

S → aS|bS|φ


Suppose L1 and L2 are two languages then the concatenation among them can be shown as:

L1L2 and they should be context-free.


L1 and L2, L = L1L2 = { anbncmdm }.

Kleene Star:

Suppose L is a context-free language, then L* is also context-free language.


L1 = { anb}*

  • Intersection− If L1 and L2 are two context-free languages, then L1 ∩ L2 is may or may not necessarily context-free.
  • Intersection with Regular Language− If L1 is a regular language and L2 is a context-free language, then L1 ∩ L2 is a context-free language.
  • Complement− If L1 is a context-free language, then L1’ may not be context-free.

Applications of Theory of Automata:

The applications of the Theory of Automata are as follows:

  1. Compiler Construction
  2. Programming Languages
  3. Linder-Mayer System
  4. Natural Language Processing

Ambiguity in Context-Free Grammar