Algorithm To Decide Whether CFL Is Empty

Spread the love

Context Free Language-


Before you go through this article, make sure that you have gone through the previous article on Context Free Language.


We have discussed-

  • Context free language is generated using a context free grammar.
  • Each context free language is accepted by a Pushdown automaton.


In this article, we will discuss a decision algorithm of CFL.


Algorithm To Decide Whether CFL Is Empty Or Not-


If we can not derive any string of terminals from the given grammar,

then its language is called as an Empty Language.

L(G) = ϕ


For a given CFG, there exists an algorithm to decide whether its language is empty L(G) = ϕ or not.




  • Remove all the useless symbols from the grammar.
  • A useless symbol is one that does not derive any string of terminals.
  • If the start symbol is found to be useless, then language is empty otherwise not.



The language generated from a CFG is non-empty iff the start symbol is generating.




Consider the following grammar-

S → XY

X → AX

X → AA

A → a

Y → BY

Y → BB

B → b


Now, let us check whether language generated by this grammar is empty or not.


The given grammar can be written as-

S → aabb

X → aX

X → aa

A → a

Y → bY

Y → bb

B → b



  • The start symbol generates at least one string (many more are possible).
  • Therefore, start symbol is useful.
  • Thus, language generated by the given grammar is non-empty.


L(G) ≠ ϕ




If L(G) = { ∈ } i.e.

  • If the language generated by a grammar contains only a null string,
  • then it is considered as non-empty.


Next Article- Algorithm To Decide Whether CFL Is Finite


Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Algorithm To Decide Whether CFL Is Empty
Article Name
Algorithm To Decide Whether CFL Is Empty
Decision Properties of Context Free Languages and Decision Algorithms for Context Free Languages- Algorithm to decide whether a Context Free Language is empty or not.
Publisher Name
Gate Vidyalay
Publisher Logo

Spread the love