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 note Theory of automata - Lecture 28 Lecture 4 Theory Of Automata By Dr. MM Alam 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 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 How to apply a recursive definition 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 2 8 is in P-EVEN by Rule 2. 8 2 10 is in P-EVEN by Rule 2. 10 2 12 is in P-EVEN by Rule 2. Method 2 We can make another definition for P-EVEN as follows Rule 1 2 is in P-EVEN. Rule 2 If x and y are both in