tailieunhanh - Lecture note Theory of automata - Lecture 10

This chapter presents the following content: Definition of GTG, examples of GTG accepting the languages of strings:containing aa or bb, beginning with and ending in same letters, beginning with and ending in different letters, containing aaa or bbb, nondeterminism, Kleene’s theorem (part I, part II, part III), proof of Kleene’s theorem part I. | Lecture # 19 Theory Of Automata By Dr. MM Alam 1 1 Lecture 18 Recap . Intersection of a regular language with another regular language also results in a regular language Proof by Demorgan’s law (Theorem 12) Theorem 12 Proof using Kleen’s theorem (UNION) Analysis of generated regular expressions Non-Regular Languages 2 Non-regular languages Let us return to. With our first assumptions we made above (that there were 95 states and that the circuit was 7 states long), we could also say that a110b96 , a117b96, a124b96 . are also accepted by this machine. All can be written the form a96(a7)mb96 where m is any integer 0,1,2,3 . If m is 0, the path through this machine is the path for the word a96b96 . 3 Non-regular languages If m is (1, that looks the same, but it loops the circuit one more time. If m 2, the path loops the circuit two more times. In general, a96(a7)mb96 loops the circuit exactly m more times. After doing this looping it gets off the circuit at exactly the same place . | Lecture # 19 Theory Of Automata By Dr. MM Alam 1 1 Lecture 18 Recap . Intersection of a regular language with another regular language also results in a regular language Proof by Demorgan’s law (Theorem 12) Theorem 12 Proof using Kleen’s theorem (UNION) Analysis of generated regular expressions Non-Regular Languages 2 Non-regular languages Let us return to. With our first assumptions we made above (that there were 95 states and that the circuit was 7 states long), we could also say that a110b96 , a117b96, a124b96 . are also accepted by this machine. All can be written the form a96(a7)mb96 where m is any integer 0,1,2,3 . If m is 0, the path through this machine is the path for the word a96b96 . 3 Non-regular languages If m is (1, that looks the same, but it loops the circuit one more time. If m 2, the path loops the circuit two more times. In general, a96(a7)mb96 loops the circuit exactly m more times. After doing this looping it gets off the circuit at exactly the same place a96b96 does and proceeds along exactly the same route to the final state. All these words, though not in L, must be accepted. 4 Non-regular languages Suppose that we had considered a different machine to accept the language L, a machine that has 732 states. When we input the word a733 b733 , the path that the a's take must contain a circuit. The word a9999b9999 also must loop around a circuit in its a-part of the path. 5 Nonregular language Suppose the circuit that the a-part follows has 101 states. Then a733+101 b733 would also have to be accepted by this machine, because its path is the same in every detail except that it loops the circuit one more time. This second machine must also accept some strings, that are not in L: a834 b733 a935 b733 a1036 b733 = a733 (a101 )m b733 6 PUMPING LEMMA (Version I) Let L be any regular language that has infinitely many words. Then there exist some three strings x, y, and z (where y is not the null string) such that all the strings of the form .