2 - Recursive Definition

Automata and Language Theory

A New Method for Defining Language Is characteristically a three step process We specify some basic objects in the set We give rules for constructing more objects in the set from the ones we already know We declare that no objects except those constructed in this way are allowed

A New Method for Defining Language Example Suppose that we are trying to define the set of

positive even integers for someone who knows about arithmetic, but has never heard of the even numbers. 

EVEN is the set of all positive who numbers divisible by 2

A New Method for Defining Language 

EVEN is the set of all 2n where n = 1 2 3 3…

by recursive definition: 

The set EVEN is defined by these three rules: Rule 1 2 is EVEN Rule 2 If x is EVEN, then so is x+2 Rule 3 The only elements in the set EVEN are those that can be produced from the two rules above

A New Method for Defining Language To prove that 14 is even  By Rule 1, we know that 2 is in EVEN  Then by Rule 2, we know that 2+2 is also in EVEN  Again by Rule 2, we know that since 4 has just been shown to e in EVEN, 4+2=6 is also in EVEN  The fact that 6 is in EVEN means that when we apply Rule 2, we deduce that 6+2=8 is in EVEN too ……..  And, at last, by applying Rule 2, yet again, to the number 12, we conclude that 12+2=14 is, indeed in EVEN

A New Method for Defining Language The set EVEN is defined by these two rules:

Rule 1 2 is in EVEN Rule 2 If x and y are both in EVEN, then so is x+y

A New Method for Defining Language Prove that 14 is in EVEN in fewer steps:

By  By  By  By  By 

rule rule rule rule rule

1, 2, 2, 2, 2,

2 is EVEN x=2, y=2, x=2, y=4, x=4, y=4, x=6, y=8,

x+y=4 is in EVEN x+y=6 is in EVEN x+y=8 is in EVEN x+y=14 is in EVEN

A New Method for Defining Language Example 

The following is a recursive definition of the positive integers Rule 1 1 is in INTEGERS Rule 2 If x is in INTEGERS, the so is x+1 (not including negatives)

A New Method for Defining Language Rule 1 1 is in INTEGERS Rule 2 If both x and y are in INTEGERS, then so are x+y and x-y Since 1-1=0 and for all positivex, o-x=-x, we see that negative integers an zero are all included in this definition

A New Method for Defining Language The set POLYNOMIAL is defined by these three

rules Rule 1 Any number is in POLYNOMIAL. Rule 2 The variable x is in POLYNOMIAL. Rule 3 If p and q are POLYNOMIAL, then so are p+q, p-q, (p), & pq Try to prove that 3x2+7x-9 is in POLYNOMIAL

A New Method for Defining Language Observe how natural the following definition are

Rule 1 x is in L1. Rule 2 If w is any word in L1, then xw is also in L1 L1=x+={x xx xxx ….}

A New Method for Defining Language Rule 1 ^ is in L4 Rule 2 if w is any word in L4, then xw is also in l4 L4=x* ….

A New Method for Defining Language The definition of Kleene closure might have

benefited from a recursive definition: Rule 1 If S is a language, then all the words of S are in S* Rule 2 ^ is in S* Rule 3 If x and y are in S*, then so is their concatenation xy.

An important Language: Arithmetic Expression ∑ - {0 1 2 3 4 5 6 7 8 9 + - * / ( )} What can you say about the following (3+5)+6) 2(/8+9) (3+(4-)8) 2)-(4

An important Language: Arithmetic Expression Recursive Definition of AE Rule 1 Any Number(+,-,0) is in AE Rule 2 If x is in AE, then so are (i) (x) (ii) –x (provided x does not already start with a - sign)

Rule 3 If x and y are in AE, then so are: (i) x + y (if the first symbol in y is not + or – (ii) x - y (if the first symbol in y is not + or – (iii) x*y (iv) x/y (v) x**y (our notation for exponentiation)

An important Language: Arithmetic Expression 

Try to prove

(2+4) * (7*(9-3)/4) / 4 * (2+8) - 1 is in AE  Prove that  An arithmetic expression cannot contain the character $  No AE can begin or end with the symbol /.  No AE can contain the substring //.

Quiz Prove that 78 is in set EVEN using the following recursive definition: Rule 1 2 and 4 are in EVEN Rule 2 If x is in EVEN, then so x+4 Give the recursive definition for the set POWER-OF-TWO = {1 2 4 8 16……}

An important Language: Arithmetic Expression

An important Language: Arithmetic Expression