Recursive Definition of a Language

A language over an alphabet Σ can be described recursively. A recursive definition has three steps:

  1. 1. Specify some basic objects in the set.
  2. 2. Specify rules for constructing more objects from the objects already knows.
  3. 3. Declaration that no objects except those constructed as given above are allowed in the set.

     Example : Let us try to define a language of positive integers.

          L = {1, 2, 3, 4, ……}

The object 2 can be derived from 1 by adding 1 to it.

The object 3 can be derived from object 2 by adding 1 to it.

     Thus, if 1 is taken as the base object then we can derive any positive integer from it.

Rules are given below :

Rule 1 : 1 is a positive integer

Rule 2 : If x is a positive integers, then so is x + 1.

Question 1:

Define a language of polynomials recursively. Given derivation for 5x2 + 7x.

Solution :

A polynomial is a finite sum of terms, where each term is of the form c . xn , c and n are integers.

           We should be able to derived a term.

Rule 1 : Any number is a term.
Rule 2 : The variable x is a term
Rule 3 : If p and q are term pq is also a term
Rule 4 : A term is polynomial
Rule 5 : If the terms p and q are in polynomial, then so are p + q and p – q.

Deriving 5x2 + 7x

             5 is a term                          -( by Rule 1)
            x is a term                          -( by Rule 2)
            5x is a term                        -( by Rule 3)
            (5x).x is a term                   -( by Rule 3)
            5x2 is a term                       -( by Rule 4)
            7 is a term                          -( by Rule 1)
            7x is a term                         -( by Rule 3)
            5x2 + 7x is a term               -( by Rule 5)


  1. Automata Theory and Formal Languages
  2. Kleene Closure
  3. Finite Representation of Language

Leave a Comment

Your email address will not be published. Required fields are marked *