Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
In this chapter, you will learn to: TGs accepting the languages: Containing aaa or bbb, beginning and ending in different letters, beginning and ending in same letters, EVEN-EVEN, a’s occur in even clumps and ends in three or more b’s, example showing different paths traced by one string, definition of GTG. | Lecture # 18 Theory Of Automata By Dr. MM Alam 1 1 Lecture 17 Recap . Regular Languages Introduction – Repeat Intersection with another language also results in a regular language 2 Theorem 12 – Repeat Statement The set of regular languages is closed under intersection. If L1 and L2 are regular languages then L1∩ L2 is also a regular language. 3 Theorem 12 – Repeat PROOF: By Demorgan’s Law For sets of any kind (regular or not) L1∩L2 = (L1' + L2')‘ L1∩L2 consists of all words that are not in L1’ or L2’. Because L1 is regular then L1’ is also regular (using Theorem 11) and so as L2’ is regular Also L1' + L2' is regular, therefore (L1' + L2')‘ is also regular (using Theorem 11) 4 Theorem 12 – Repeat Two languages over Σ = {a,b} L1 = all strings with a double a L2 = all strings with an even number of a's. L1 and L2 are not the same, since aaa is in L1 but not in L2 and aba in in L2 but not in L1 Example 5 Theorem 12 – Repeat L1 and L2 are regular languages defined by the regular . | Lecture # 18 Theory Of Automata By Dr. MM Alam 1 1 Lecture 17 Recap . Regular Languages Introduction – Repeat Intersection with another language also results in a regular language 2 Theorem 12 – Repeat Statement The set of regular languages is closed under intersection. If L1 and L2 are regular languages then L1∩ L2 is also a regular language. 3 Theorem 12 – Repeat PROOF: By Demorgan’s Law For sets of any kind (regular or not) L1∩L2 = (L1' + L2')‘ L1∩L2 consists of all words that are not in L1’ or L2’. Because L1 is regular then L1’ is also regular (using Theorem 11) and so as L2’ is regular Also L1' + L2' is regular, therefore (L1' + L2')‘ is also regular (using Theorem 11) 4 Theorem 12 – Repeat Two languages over Σ = {a,b} L1 = all strings with a double a L2 = all strings with an even number of a's. L1 and L2 are not the same, since aaa is in L1 but not in L2 and aba in in L2 but not in L1 Example 5 Theorem 12 – Repeat L1 and L2 are regular languages defined by the regular expressions below. r1 = (a + b)*aa(a + b)* r2 = b*(ab*ab*)* A word in L2 can have some b’s in the front But whenever there is an a, it balanced by an other a (after some b’s). Gives the factor of the form (ab*ab*) The words can have as many factors of this from as it wants. It can end an a or ab. Example 6 Theorem 12 – Repeat These two languages can also be defined by FA (Kleen’s theorem) Example FA1 FA2 7 Theorem 12 – Repeat In the proof of the theorem that the complement of a regular language is regular an algorithm is given for building the machines that accept these languages. Now reverse what is a final state and what is not a final state. The machines for these languages are then (see the next slide ) 8 Theorem 12 – Repeat Recall that how we go through stages of transition graphs with edges labeled by regular expressions. Thus, FA1' becomes: 9 Theorem 12 State q3 is part of no path from - to +, so it can be dropped. We need to join incoming a edge with both outgoing edges(b to q1 and q2
