tailieunhanh - Lecture note Theory of automata - Lecture 28

The following will be discussed in this chapter: Examples of Myhill Nerode theorem, Quotient of a language, examples, Pseudo theorem: Quotient of a language is regular, prefixes of a language, example. | Lecture # 4 Theory Of Automata By Dr. MM Alam 1 Lecture#3 Recap Plus Operation Examples Four way of defining languages Examples for Descriptive way of defining languages Recursive way A recursive definition is fundamentally a three-step process: We specify some basic objects in the set. The number of basic objects specified must be finite. This means that we write some basic facts about the set Second, we give a finite number of basic rules for constructing more objects in the set from the ones we already know. Finally, we provide declaration that no objects except those constructed in this way are allowed in the set. Language of Integer Defining language of INTEGER Rule 1: 1 is in INTEGER. Rule 2: If x is in INTEGER then x+1 and x-1 are also in INTEGER. Rule 3: No strings except those constructed in above, are allowed to be in INTEGER. Defining the language L, of strings beginning and ending in different letters , defined over Σ={a, b} Rule 1: ab and ba are in L Rule 2: (a)s(b) and . | Lecture # 4 Theory Of Automata By Dr. MM Alam 1 Lecture#3 Recap Plus Operation Examples Four way of defining languages Examples for Descriptive way of defining languages Recursive way A recursive definition is fundamentally a three-step process: We specify some basic objects in the set. The number of basic objects specified must be finite. This means that we write some basic facts about the set Second, we give a finite number of basic rules for constructing more objects in the set from the ones we already know. Finally, we provide declaration that no objects except those constructed in this way are allowed in the set. Language of Integer Defining language of INTEGER Rule 1: 1 is in INTEGER. Rule 2: If x is in INTEGER then x+1 and x-1 are also in INTEGER. Rule 3: No strings except those constructed in above, are allowed to be in INTEGER. Defining the language L, of strings beginning and ending in different letters , defined over Σ={a, b} Rule 1: ab and ba are in L Rule 2: (a)s(b) and (b)s(a) are also in L, where s belongs to Σ* Rule 3: No strings except those constructed in above, are allowed to be in L Factorial Example Lets consider the language of factorial: Rule 1: We know that 0!=1, so 1 is in factorial. Rule 2: Also n!=n*(n-1)! is in factorial. Rule 3: Thus, no strings except those constructed in above, are allowed to be in factorial. Consider the set P-EVEN, which is the set of positive even numbers. Method#1: We can define P-EVEN to be the set of all positive integers that are evenly divisible by 2. OR P-EVEN is the set of all 2n, where n = 1, 2, . . P-EVEN is defined by these three rules: Rule 1: 2 is in P-EVEN. Rule 2: If x is in P-EVEN, then so is x + 2. Rule 3: The only elements in the set P-EVEN are those that can be produced from the two rules above. In particular, to show that 12 is in P-EVEN using the last definition, we would have to do the following: 2 is in P-EVEN by Rule 1. 2 + 2 = 4 is in P-EVEN by Rule 2. 4 + 2 = 6 is in P-EVEN by Rule 2. 6