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.
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,
that was explained too well mate thanks for the help...
ReplyDelete