.well-known

This is a Brave Rewards publisher verification file. Domain: mathematicsway.blogspot.com Token: 61623a436e7c44ba1310544150d3db370336fd3a7242d9db2869ad9e33470742

Followers

Thursday, December 29, 2011

AUTOMATA : RECURSIVE DEFINITION


RECURSIVE DEFINITION            
                  – is characteristically a three-step process.  
       1)   specify some basic objects in the set.   
      2)  Give rules for constructing more objects in the set from the ones we already know.  
      3)  Declare that no objects except those constructed in this way are allowed in the set.    

Recursive language
A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP.
This type of language was not defined in the Chomsky hierarchy of (Chomsky 1959).

Definitions

There are two equivalent major definitions for the concept of a recursive language: A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.

A recursive language is a formal language for which there exists a Turing machine which will, when presented with any input string, halt and accept if the string is in the language, and halt and reject otherwise. The Turing machine always halts; it is known as a decider and is said to decide the recursive language.

All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.

Closure properties

Recursive languages are closed under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well: 
 
                            

The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.


If we try to define a set of even positive integers. One standard way of defining this set is :
EVEN is the set of all positive whole numbers divisible by 2; or EVEN is the set of all 2n,
 where  n = 1 2  3  4 . . .  A third method is by recursive definition. EVEN is defined by these three rules:

      Rule  1 :  2 is in EVEN.
      Rule  2 :  If  x is EVEN  then so  is  x + 2.
      Rule  3 :  The only elements in the EVEN are those that can be produced from the two rules above.


  Ex. 1.  Prove that 10  is in the EVEN set.
By defn 1) divide 10 by 2, there is no remainder; hence 10 is in EVEN set
By defn 2) 10 = ( 5 )( 2 ) ; hence 10 is in EVEN.
By defn 3) recursive definition :  by rule 1, we know  2 is in EVEN; then by rule 2  we know that
 2 + 2  = 4  is in EVEN.  Since 4 is in EVEN then by rule  2 ,   4 + 2 = 6 is in EVEN. By rule 2,
 6 + 2  = 8  is in EVEN. By rule 2 ,  8 + 2 = 10 is in EVEN set; hence 10  is in EVEN. 




Alternately; the set EVEN is defined by these rules :
   Rule 1 :  2  is  in EVEN.
   Rule 2 :  If  x  and  y  are both in EVEN then so is   x  +  y.
   Rule 3 :  No number is in EVEN unless it can be produced by Rules  1  and  2.

 To solve the above example :

  By rule  1 :  2  is  in  EVEN
  By rule  2 :  x = 2 ,  y = 2  --->  4  is in EVEN
  By rule  2 :  x = 2 ,  y = 4  --->  6 is in EVEN
  By rule  2 :  x = 4 ,  y = 6  ---> 10  is in EVEN. 


 A polynomial is a finite sum of terms each of which is of the form a real number times a 
  power of x  ( that may be  x0 = 1 ).


     The set POLYNOMIAL  is defined by these four rules :
            Rule 1 :  Any number is in POLYNOMIAL.
            Rule 2 :  The variable x is in POLYNOMIAL.
            Rule 3 :  If  p  and  q  are in POLYNOMIAL, then so are  p + q  and ( p ) and  pq.
            Rule 4 :  POLYNOMIAL contains only those things which can be created by the 3 rules above.

   Ex. 2.  Show that  7x2  +  3x – 2  is in POLYNOMIAL.
     By rule  1 :  7  is in POLYNOMIAL          
     By rule  2 :  x  is in POLYNOMIAL
     By rule  3 :  ( 7 )( x ) is in POLYNOMIAL, call it  7x
     By rule  3 :  ( 7x )( x ) is in POLYNOMIAL,  call it  7x2   
     By rule  1 :  3  is in POLYNOMIAL
     By rule  3 :  ( 3 )( x )  is in POLYNOMIAL
     By rule  3 :  7x2  +  3x  is in POLYNOMIAL. 
     By rule  1 :   –2  is  in POLYNOMIAL
     By rule  3 :  7x2  +  3x  + (–2 ) = 7x2  +  3x  – 2  is in POLYNOMIAL.

  Ex.  3.  Show that  26  is in EVEN set
  Ex.  4.  Show that  x2 – 3x  +  2  is in POLYNOMIAL.  
  Ex.  5.  Show that  7x2  +  3x  –  11  is in POLYNOMIAL.
  Ex.  6.  Show that   x2 – 12x  +  18  is in POLYNOMIAL.

Arithmetic Expressions ( AE )
            Supposed we ask ourselves what constitutes a valid arithmetic expressions that can be typed on one line, in a form digestible by computers. The alphabet of this language is :
            S = { 0  1  2  3  4  5  6  7  8  9    +      *   /   (   )   }
  It is obvious that the following strings are not good :
            ( 3 + 5 )  + 6 )              2( /8  +  9 )                 
            ( 3 + ( 4 - ) 8 )              2 ) – ( 4 

   ( 3 + 5 )  + 6 ) – contains an unbalanced parenthesis.                      
   2( / 8  +  9 ) – contains a forbidden substring  ( /
   ( 3 + ( 4  – ) 8 )  – contains the forbidden substring  – )                   
   2 )  –  ( 4   –  contains  a close parenthesis before the corresponding open parenthesis.
//  and  */  are also forbidden in arithmetic expressions.
            The most natural way of defining a valid arithmetic expression is by using recursive definition.

The definition can be written as :
            Rule 1 :  Any number of ( positive, negative, or zero ) is in AE.
            Rule 2 :  If x is in AE, then so are ( x )  and  – ( x ).
            Rule 3 :  If  x  and  y  are in AE, then so are
                        ( i )  x + y  ( if the first symbol in y is not  – )
                        ( ii )  x – y  ( if the first symbol in y is not  – )
                        ( iii )  x * y
                        ( iv )  x / y
                        ( v )  x ** y   ( our notation for exponentiation )
   This is the most natural definition because even if we have not articulated at this point, it truly is the method for recognizing arithmetic expression in real life. Given the expression with
                                                ( 2 + 4 ) * ( 7 * ( 12 –  4 ) / 4 * 2 ( 2 + 8 ) – 1   
      and asked to determine if it is a valid expression, we do not really scan over the string looking for forbidden     
      substrings or count the parentheses. This can broken down into components and verify whether it is ok or not. 

     Clear expressions :     2 + 3 + 4 ,     12 – 3 + 4
     Ambiguous expressions :   8/4/2  which may be equal to  4  or  1
                                                3 + 4 * 5  which may be equal to  23 or 35

    Hence, we adopt conventions for operator hierarchy and left to right execution.  By applying Rule 2, we can place enough parenthesis to avoid any confusion. This definition adequately defines the language of all valid strings of symbols for arithmetic expressions.  Remember that the ambiguity in the string  8/4/2 is a problem of meaning.  There is no doubt that the string is a word in AE, only doubt about what it means. This definition determines the set AE in a manner useful for proving many theorems about arithmetic expressions.

   Theorem 2 : An arithmetic expression cannot contain the character $.

     Proof by constructive algorithm:
            $ is not part of any number, so it cannot be introduced into an AE by Rule 1. If the character string x does not contain the character $, then neither do the strings ( x ) and – ( x ), so it cannot be introduced into an AE by Rule 2. If neither  x  nor  y contains the character  $, then neither do any of the expressions defined by Rule 3. Therefore, the character $ can never get into an AE.

   Theorem 3 :  No  AE can begin or end with the symbol /.
    
     Proof by constructive algorithm:
               No number begins or ends with this symbol, so it cannot occur by Rule 1. Any AE formed by Rule 2 must begin and end with parentheses or begin with a minus sign, so the / cannot be introduced by Rule 2. If x does not begin with a / and y does not end with a /, then any AE formed by any clause in Rule 3 will not begin or end with a /. Therefore, these rules will never produce an expression beginning or ending with a /.      

( The symbol / in computer science is “slash”, other names are “oblique stroke”, “solidus” or “virgule”).

 Theorem 4 :  No AE can contain the substring //.
 Proof :  For variation, we shall prove this by contradiction, even though a direct argument similar to those above could easily be given.
           Let us suppose that there were some AE’s that contained the substring //, but there is no shorter word in AE that contains this substring. There may be more strings of the same length as w that contains //, but it does not matter which of these we begin with and choose to call w.
           We know that w like all words in AE, is formed by some sequence of applications of the Rules 1, 2 and 3. The first question is:   Which was the last rule used in the production of w ?  It must have been Rule 3(iv). If it were Rule 3(iii), for instance, then the double slash must either be found in the x part or the y part. But x and y are presumed to be in AE so this would mean that there is some shorter word in AE than w that contains the substring //, which contradicts the assumption that w is the shortest, similarly, we can eliminate all the other possibilities. Therefore the last rule used to produce  w  must have been 3 (iv).

           Now, since the // can have been contributed to w from the  x  part alone or from the  y  part alone ( or else x or y)  are shorter words in AE with a double slash , it must have been included by finding an x part that ended in / or a y part that begin with a /. But since both x and y are AE’s, our previous theorem says that neither case can happen. Therefore even Rule 3(iv) cannot introduce the substring //.
     Therefore, there is no possibility left for the last rule from which w can be constructed. Therefore, w cannot be in the set AE. Therefore there is no shortest AE that contains the substring //. Therefore, nothing in the set AE can have the substring //.     

This method of argument is familiar. It is similar to the proof that { xx, xxx }* contains all  xn , for n is not = to 1. 
Another common use of the recursive definitions is to determine what expressions are valid in Symbolic Logic. We shall be interested in one particular branch of Symbolic Logic called Sentential Calculus or the Propositional Calculus. The version we shall use here uses only negation  ~  and implication --->  along with the phrase variables, although conjunction and disjunction could easily be added to the system. The valid expressions in this language are traditionally called WFF’s for Well-Formed Formulas. As with AE, parentheses are letters in the alphabet.
                                         

   


 
Bibliography :
   1.  Rich, Elaine ( 2009 ) . Automata, Computability and Complexity. New Jersey : Pearson Prentice Hall
   2.  Cohen, Daniel I. A. ( 1991 ) . Introduction to Computer Theory  . New York : John Wiley and Sons
   3.  Brookshear, J. Glenn . ( 1989 ) Theory of Computation, Formal languages, Automata, and Complexity. Redwood City,




RELATIONS AND DIGRAPHS


4 : RELATIONS  AND DIGRAPHS  
 4.1  Product sets 
             An ordered pair ( a , b ) is a listing of the objects a and b in a prescribed order, with  a  appearing first and b appearing second.  Thus an ordered pair is merely a sequence of length 2. The ordered pairs  ( a1 , b1 )  and  ( a2 , b2 )  are equal if and only if  a1 = a2  and  b1 = b2
             If  A  and  B  are two nonempty sets,  then the product set  or Cartesian product  A x B  as the set  of all ordered pairs ( a , b ) with  a Î A  and  b Π B.  Thus,
A  x  B  = {  ( a , b ) |  a Î A  and  b Π B } .
Example 1:
          Let  A = { 1 , 2 ,  3 , 4 }            and    B  =  {  w , x }   then
                        A  x  B  =  { ( 1, w) , ( 1, x ) ,  ( 2, w ) , ( 2, x ) ,  ( 3, w ) ,  ( 3, x ) , ( 4, w ) ,  ( 4, x ) }

    Observe that the elements of  A x B can be arranged in convenient tabular array as shown :
                                 

     B
 A

      w

          x
        1
     ( 1 , w )
     ( 1 , x )
        2
     ( 2 , w )
     ( 2 , x )
        3
     ( 3 , w )
     ( 3 , x )
        4
     ( 4 , w )
     ( 4 , x )
 
Example  2 :
            If  A and B are  as in Example 1, then
                   B  x  A =  { ( w, 1) , ( x, 1 ) ,  ( w, 2 ) , ( x, 2 ) ,  ( w, 3 ) ,  ( x, 3 ) , ( w, 4 ) ,  ( x, 4 ) }

  Theorem  1 : For any two finite, nonempty sets A and B,  | A x B |  =  | A | | B |     
        Proof :
            Suppose that | A | = m  and | B |  =  n. To form an ordered pair ( a, b ), a Î A  and  b Î B, perform two successive tasks.  Task 1 is to choose a first element from A, and task 2 is to choose a second element from B. There are m ways to perform task 1 and n ways to perform task 2; so by the multiplication principle, there are m x n ways to form an ordered pair ( a, b ).
            In other words, | A x B | = m × n  = | A | | B |.

Example 3.
          If  A = B = R, the set of all real numbers, then  R x R, also denoted by R 2, is the set of all points in the plane. The ordered pair ( a , b ) gives the coordinates of a point in the plane.     

Example 4 :
 A marketing research firm classifies a person according to the following two criteria :
    Gender : male ( m ) ; female ( f )
    Highest level of education completed : elementary ( e ) ; high school ( h ) ; college ( c ) ; graduate ( g )
 Let  S = { m , f } and L { e , h , c , g } .  The product set  S x L  contains all the categories into which the population is classified.  Thus, the classification ( f, g ) represents a female who has completed graduate school. There are eight categories in this classification scheme.
      We now define the Cartesian product of three or more nonempty sets by generalizing the earlier definition of the Cartesian product of two sets. That is, the Cartesian product  A1 x  A2 x . . . x  Am of the nonempty sets  A 1,  A 2, . . . , A m  is the set of all ordered m – tuples  ( a 1, a 2, . . ., a m ),  where a i Î A i for    i = 1, 2, . . . , m. Thus   A 1 x  A 2 x . . . x  A m  = { ( a 1, a 2, . . . , a m ) | a i Î A  i  ,  i = 1, 2, . . . , m } .  

Example 5 :
      A software firm provides the following three characteristics for each program that it sells :
            Language : FORTRAN ( f ) ;  PROLOG ( p ) ; LISP ( l )
            Memory :  2 meg ( 2 ) ;  4 meg ( 4 ) ;  8 meg ( 8 )
            Operating system : UNIX ( u ) ; DOS ( d )
     Let  L = { f , p , l } ,  M = { 2 , 4 , 8 }  and  O = { u , d } . Then the Cartesian product  L x M x O contains all the categories that describe a program. There are 3 × 3 × 2 or 18 categories in this classification scheme.

            Proceeding in a manner similar to that used to prove Theorem 1, using the extended multiplication principle, we can show that if A1 has n1 elements, A2 has  n2 elements, . . . , A m has  nm elements then  A1 x  A2  x . . . x  Am  has  n1 , n2 , . . . nm  elements.

PARTITIONS
    A partition or quotient set of a nonempty set A is a collection  P  of nonempty subsets of A such that
            1.  Each element of A belongs to one of the sets in P.    
            2.  If  A1  and  A2 are distinct elements of P, then     
                                                                 A 1 ∩ A 2 = Ø

          The  sets in  P  are called the blocks or cells of the partition. 
The figure shows a partition  P = { A1,  A2,  A3,  A4,  A5,  A6,  A7 } into seven blocks.  

Example 6 :
      Let  A = { s,  t,  u,  v,  w,  x,  y,  z } .  Consider the following subsets of A :
            A 1 = { s,  t,  u,  v } ;  A 2  =  { s,  u,  w,  x,  y,  z } ;  A 3 = { s,  u, w,  y } ;  
             A 4 = { t,  v } ; A 5 = { x, z } 
Then  { A 1 , A 2 } is not a partition since
                                                        A 1 ∩ A 2 is not = Ø.
Also,  { A 1 , A 5 } is not a partition since w Ï A 1 and  w Ï A 5
 The collection  P = { A 3 , A 4 , A 5 } is a partition of A.

Example 7.
            Let         Z   = set of all integers.
                        A 1  = set of all even integers, and
                        A 2  = set of all odd integers.
            Then  {  A 1 ,  A 2 }  is a partition of Z. 

Since the members of a partition of a set are subsets of A, we see that the partition is a subset of P ( A ), the power set of A. That is, partitions can be considered as particular kinds of subsets of P ( A ).

Exercises : 4.1 p 105
In # 1 – 4, find x or y so that the statement is true.
     1.  a)  ( x , 3 ) = ( 4 , 3 )                            b)  ( a , 3y ) = ( a , 9 )
     2.  a)  ( 3x + 1 , 2 ) = ( 7 ,  2 )                  b)  ( C + + , LISP ) =  ( y , x ) 
     3.  a)  ( ( 4x , 6 ) = ( 16 , y )                     b)  ( 2x – 3 , 3y – 1 ) = ( 5 , 5 )
     4.  a)  ( x 2 , 27 )  =  (  49 , y 3 )                b)  ( x , y ) = ( x 2 , y 2 )
          Let  A = {  a,  b }   and    B = {  3 ,  5 ,  7 }
     5.  List the elements in  a)  A  x  B    and   b )  B  x  A
     6.  List the elements in  a)  A  x  A    and   b)  B  x  B    

      In the next exercises, let  A = { 1,  2,  3,  4,  5,  6, 7,  8,  9, 10 }  and
             A 1 =  { 1, 2, 3, 4 }                 A 3  =  { 4, 5, 7, 9 }                   A 5  =  {  8,  9,  10 }       
             A 2 =  { 5, 6, 7 }                     A 4  =  { 4, 8, 10 }                     A 6  =  { 1, 2, 3, 6, 8, 10 }
 7.  Which of the following are partitions of A ?
          a)  {  A1, A2 ,  A 5 }        b)  {  A1, A3 ,  A5 }     c) {  A3, A6 }       d) {  A2, A3 ,  A4 }

RELATIONS AND DIGRAPHS
          Let A and B be nonempty sets. A relation  R  from  A  to  B is a subset of  A x  B. If  R Í A  x  B and  ( a,  b )  Î R, we say that  a  is related to b by R, and we also write  a R b.  If a is not related to b by R, we write a R b.    ( R/ )
 Example 1.     
        Let  A = { 1, 2, 3 } and B = { w, x }. Then  R = { ( 1 , w ), ( 2 , x ),  ( 3, w ) }  is a relation from A to B.
 Example  2 :
          Let A and B be sets of real numbers . We define the following relation R ( equals )  from A to B.:
                                              a R b   if and only if  a = b.
 Example 3 :
        Let  A = { 1,  2,  3,  4,  5 }. Define the following relation R ( less than ) on A :
                                              a R b  if and only if  a < b.
  Then,  R = { ( 1, 2 ), ( 1, 3 ), ( 1, 4 ), ( 1, 5 ), ( 2, 3 ), ( 2, 4 ), ( 2, 5 ), ( 3, 4 ), ( 3, 5 ), ( 4, 5 ) }

 Example 4 :
        Let  A = Z + ,  the set of all positive integers. Define the following relation R on A :
                                                a R b   if and only if  a  divides  b
   Then,  4 R 12 ,  but  5 is not R 7       ( R/ )

 Example 5 :  
       Let A be the set of all people in the world. We define the relation  R on A,  a R b  if and only if there is a sequence  a 0,  a 1, . . . , a n  of people such that a 0 =  a,  a n =  b  and  a i – 1 knows  i =  1, 2, . . ., n     ( n will depend on a and b )

 Example  6 :

       Let  A = , the set of real numbers. We define the following relation  R on A :

                          x R y   if and only if  x  and  y  satisfy the equation 


                                            
                           
The set R consists of all points on the ellipse shown in the figure.

Example 7 :
    Let A be the set of all possible inputs to a given computer program. Define the following relation R from A to B :  a R b  if and only if b is the output produced by the program when input a is used.

Example  8 :
    Let A = the set of all lines in the plane. Define the following relation
R on A :

                                                     L1 R  L2   if and only if  L1 is parallel to L2.

    
     Example 9 :
         An airline services the five cities c 1, c 2, c 3, c 4, and c 5. The cost ( in dollars ) of going from ci to cj is shown in the following table.  Thus, the cost of going from c 1 to c 3  is  $ 100, while that of  c 4  to  c 2  is $ 200.    

                                         

   To
From

C1

C2

C3

C4

C5
C1

150
110
160
210
C2
200

210
170
230
C3
120
190

200
260
C4
200
210
130

160
C5
210
110
210
160


 
We now define the following relation R on the set of cities 
       A =  { C 1 , C 2 , C 3, C 4 , C 5 } : ci R cj if and only if the cost of going from  ci   to cj is defined and less than or equal to  $190.  Find R.

Solution :
            The relation R is the subset of A x A consisting of all cities ( ci , cj),  where the cost of going from ci to cj is less than or equal to  $ 190. Hence ; 
   R = { (c 1, c 2 ), (c 1, c 3 ), (c 1, c 4) , (c 2 , c 4), (c 3, c 1), (c 3, c 2 ), (c 4 , c 3), (c 4, c 5),  (c 5, c 2), ( c 5 , c 4 ) }


Sets Arising from Relations
        1.  Domain of R.  Dom ( R ), is the set of all elements in A that are related to some element in B. It is a subset of A, it is the set of all first elements in the pairs that make up R.
        2.  Range of R. Ran ( R ), is the set of elements in B that are second elements of pairs in R, that is, all elements in B that are related to some elements in A.

            Elements in A that are not in Dom ( R ) are not involved in the relation R in any way. This also true for elements of B That are not in Ran ( R ).
Example :
        Let  A = { 1,  2,  3,  4,  5 }.  a R b  if and only if  a < b.
  Then, R = { (1, 2 ), ( 1, 3 ) , ( 1, 4 ) , ( 1, 5 ), ( 2, 3) , ( 2, 4 ) , ( 2, 5 ), ( 3, 4 ), ( 3, 5 ), ( 4, 5 ) }
            Also Dom ( R ) = { 1, 2, 3, 4 } and  Ran ( R ) = { 2, 3,  4, 5 }

In example 6 ( ellipse ) :
     DOM ( R )  = [ –2, 2 ] and  Ran ( R ) = [ –3, 3 ]. Note that this is given in interval notation.
If R is a relation from A to B and  x  Π A , we define R ( x ), the R–relative set of x, to be the set of all y in B with the property that x is R–related to y. Thus, in symbols,

                                                R ( x ) = { y  Î  B  |  x R y  }

Similarly, if  A1  Í  A, then R ( A1 ), the  R – relative set of A1, is the set of all y in B with the property that x is  R – related to y for some x in A1, that is,
                                                R ( A1 ) ={ y  Î  B  |  x R y  for some x in A1 }  

From the preceding definitions, we see that R ( A1 )  is the union of the sets  R ( x ),  where  x  Î  A1. The sets   R ( x )  play an important role in the study of many types of relations.

Let  A = { w,  x,  y,  z } and  let  R = { ( w, w ), ( w,  x ), ( x,  y ),  ( y,  w ),  ( z,  y ),  ( y,  x ) }
Then R ( w ) = { w , x } ,  R ( x ) = { y } ,  and if  A 1 = { y , z } , then  R ( A 1 ) = { w , x ,  y }  

Let R be the relation in example 6 ( ellipse ), and let  x  Π .  If  x R y for some y, then  


            If  x is not in the interval (– 2, 2 ) then no y can satisfy the equation, since

                                            
Thus, in this case R ( x ) = { 0 } .  If  x = – 2 , then x 2 / 4  = 1, so x can only be related to 0. Thus, R (– 2 ) = { 0 } .  Similarly, R ( 2 ) = { 0 }.