Tag: Algorithm to decide whether CFL is finite

Algorithm To Decide Whether CFL Is Finite

Theory of Automata & Computation

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 Finite Or Not-

 

For a given CFG, there exists an algorithm to decide whether its language is finite or not.

 

Step-01:

 

Reduce the given grammar completely by-

  • Eliminating ∈ productions
  • Eliminating unit productions
  • Eliminating useless productions

 

Also Watch- How To Reduce Grammar?

 

Step-02:

 

  • Draw a directed graph whose nodes are variables of the given grammar.
  • There exists an edge from node A to node B if there exists a production of the form A → αBβ.

 

Now, following 2 cases are possible-

 

Case-01:

 

  • Directed graph contains a cycle.
  • In this case, language of the given grammar is infinite.

 

Case-02:

 

  • Directed graph does not contain any cycle.
  • In this case, language of the given grammar is finite.

 

Also Read- Algorithm To Decide Whether CFL Is Empty

 

PRACTICE PROBLEMS BASED ON DECIDING WHETHER CFL IS FINITE-

 

Problem-01:

 

Check whether language of the following grammar is finite or not-

S → AB / a

A → BC / b

B → CC / c

 

Solution-

 

Step-01:

 

The given grammar is already completely reduced.

 

Step-02:

 

We will draw a directed graph whose nodes will be S , A , B , C.

 

Now,

  • Due to the production S → AB, directed graph will have edges S → A and S → B.
  • Due to the production A → BC, directed graph will have edges A → B and A → C.
  • Due to the production B → CC, directed graph will have edge B → C.

 

The required directed graph is-

 

 

Clearly,

  • The directed graph does not contain any cycle.
  • Therefore, language of the given grammar is finite.

 

Problem-02:

 

Check whether language of the following grammar is finite or not-

S → XS / b

X → YZ

Y → ab

Z → XY

 

Solution-

 

Step-01:

 

The given grammar is already completely reduced.

 

Step-02:

 

We will draw a directed graph whose nodes will be S , X , Y , Z.

 

Now,

  • Due to the production S → XS / b, directed graph will have edges S → X and S → S.
  • Due to the production X → YZ, directed graph will have edges X → Y and X → Z.
  • Due to the production Z → XY, directed graph will have edges Z → X and Z → Y.

 

The required directed graph is-

 

 

Clearly,

  • The directed graph contain cycles.
  • Therefore, language of the given grammar is infinite.

 

Next Article- CYK Algorithm

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.