CFG Properties and Applications

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


We are a team of writers, researchers, and editors who are passionate about helping others live their best lives. We believe that life is a beautiful gift. We try to live our lives to the fullest and enjoy every moment. We are always learning and growing, and we cherish the relationships we have with our family and friends.

Leave a Reply