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

- 1. Specify some basic objects in the set.
- 2. Specify rules for constructing more objects from the objects already knows.
- 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 5x^{2} + 7x.

**Solution :**

A polynomial is a finite sum of terms, where each term is of the form c . x^{n} , **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 5x**^{2} + 7x

^{2}+ 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)**

5x^{2} is a term **-( by Rule 4)**

7 is a term **-( by Rule 1)**

7x is a term **-( by Rule 3)**

5x^{2} + 7x is a term ** -( by Rule 5)**