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 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)
