Report

3.3 Closure Properties of Regular Languages Given regular languages L 1 and L 2, we will show that L 1 L 2, L 1 L 2, the complement of L 1and L 1 \ L 2 are regular. Sometimes, we can apply the closure properties to show some sets are not regular. Theorem 3 : Regular languages are closed under union operation and Kleene star operation. Proof: If L 1 and L 2 are regular, then there are regular expressions r 1 and r 2 denoting the languages L 1 and L 2 ,respectively. ( r 1+ r 2) and (r 1*) are regular expressions denoting the languages L 1 L 2 and L 1*. Therefore, L 1 L 2 and L 1* are regular. Theorem 4 : Regular languages are closed under complement operation and intersection operation. Proof: Suppose that L 1 and L 2 are regular over an alphabet . There is a DFA M=(Q, , , q 0, F) accepting L 1. Design a DFA M’ = (Q, , , q 0, F’), where F’ = Q \ F. Now, we have that L(M’) = * \ L 1. Hence, the complement of L 1 is regular. Let L 1’ = * \ L 1 and L 2’ = * \ L 2. The complement of L Hence 1’ L 2’ is regular and is equal to L 1 L 2 . L 1 L 2 is regular. The proof of regular languages are closed under intersection operation can be done by construct a new DFA to accept the intersection. The construction is as follows. Suppose that L 1 and L 2 are regular languages accepted by DFA’s M 1=(Q 1, , 1, q 0 1, F 1) and M 2 =(Q 2, , 2, q 0 2, F 2) such that L(M 1) = L 1 and L(M 2 )= L 2. Construct a DFA M = (Q, , , q 0, F ), where Q = Q 1 Q 2, q 0 = (q 0 1, q 0 2), F = F 1 F 2, and ((p i, q s), a) = ( 1(p i, a), 2(q s, a)). It is not difficult to show that L(M) = L 1 L 2. Example 9: Let L = { {0, 1}* | the number of 0’s in is equal to the number of 1’s in }. Show that L is not regular. Solution : Assume that L were regular. Let L’ = L L(0 + 1 +). L’ = { 0 i1 i | i > 0 }. Since L and L (0 + 1 +) are regular, we have that L’ is regular. By example 6 in section 3.2 we know that L’ is not regular , a contradiction. Therefore, L is not regular. Example 10: Let L = {0 k | k is a composite integer}. Show that L is not regular. Solution : Let L’ = {0 k | k is a prime integer}. Then L = {0}* \ L’ \ {0}. Assume that L’ were regular. Let n be the constant in the pumping lemma. Choose = 0 s, where s = p n, p n is the nth prime number . Let = xyz, where |xy| n and |y| 1. Hence, x = 0 |x| and y = 0 |y|. Consider the case that i = p n + 1, |xy i z| = p n + p n |y| = p n (|y|+1), not a prime number. Hence, contradict to that L’ is regular. Therefore, L is not regular.