tailieunhanh - Lecture note Theory of automata - Lecture 11

Lecture Theory of automata - Lecture 8 presents the following content: Proof of Kleene’s theorem part II (method with different steps), particular examples of TGs to determine corresponding Res. | Lecture # 20 Theory Of Automata By Dr. MM Alam 1 1 Lecture#19 Recap Pumping Lemma 1 Examples Need for Pumping Lemma Version II Theorem 15 Given a language L, we shall say that any two strings x and y are in the same class if for all possible strings z either both xz and yz are in L or both are not. The language L divides the set of all possible strings into separate classes. If L is regular the number of classes L creates is finite. If the number of classes L creates , is finite then L is regular. 3 Theorem 15 Example 1 Let us consider a language of all words that end with an a , at first it may seem that there is only one class here because for all x and y , both xz and yz end an a or not, depending on z alone. But this overlooks the fact that if z is ʎ. Then xz and yz are in the same class depending on whether x and y end an a themselves. There are therefore two classes. C1 = all strings that end an a, a final state. C2 = all strings that don't, the start state. 4 Theorem 15 Example | Lecture # 20 Theory Of Automata By Dr. MM Alam 1 1 Lecture#19 Recap Pumping Lemma 1 Examples Need for Pumping Lemma Version II Theorem 15 Given a language L, we shall say that any two strings x and y are in the same class if for all possible strings z either both xz and yz are in L or both are not. The language L divides the set of all possible strings into separate classes. If L is regular the number of classes L creates is finite. If the number of classes L creates , is finite then L is regular. 3 Theorem 15 Example 1 Let us consider a language of all words that end with an a , at first it may seem that there is only one class here because for all x and y , both xz and yz end an a or not, depending on z alone. But this overlooks the fact that if z is ʎ. Then xz and yz are in the same class depending on whether x and y end an a themselves. There are therefore two classes. C1 = all strings that end an a, a final state. C2 = all strings that don't, the start state. 4 Theorem 15 Example 2 Let L be a language of all string that contain double a, there are three classes C1 = strings without aa that end in a. C2 = strings without aa that end in b or ʎ. C3 = strings with aa, the final state. 5 Theorem 15 Example 3 Working the algorithm of theorem 15 on the language EVEN – EVEN creates 4 obvious states. C1 = EVEN-EVEN C2 = even a’s , odd b’s C3 = odd a’s , even b’s C4 = odd a’s, odd b’s Clearly if x and y are in any one class, then both xz and yz are in L or not, depending on how many a’s and b’s z alone has. 6 Theorem 15 Example 4 To show that the language anbn is not regular, we need to observe that the string a, aa, aaa, aaaa, are all in different classes. Because for each m only am is turned into a word in L by z = bm 7 Theorem 15 Example 5 To show that anban is a nonregular We note that the string ab, aab, aaab, . . . All are in different classes because for each of them one value of z = am will produce a word in L and leaves the others out of L. Example 6 EQUAL .