1 The nor of two languages is norL1 L2 w w 6 L1 and w 6 L2

1. The nor of two languages is:

nor(L1, L2) = {w : w 6 L1 and w 6 L2}

Show that the family of regular languages is closed under the nor operation.

2. Show that if L is regular, then the language tail is also regular,

where tail(L) = {y : xy : L for some x }

Solution

1.

We have that the reverse language of L2/L1 is (L2/L1) R = {y R : y Rx R L R 1 , xR L R 2 } = L R 1 /LR 2 . If L1 and L2 are regular, from the result of homework 1-(12), we have that L R 1 and L R 2 are regular. Now, because the right-quotient of L R 1 with L R 2 , i.e., L R 1 /LR 2 , is regular (from Theorem 4.4 in the textbook), we have that (L2/L1) R is regular. Again, from the result of homework 1-(12), we have that ((L2/L1) R) R = L2/L1 is regular.

2.
For LU , if L1, L2, . . ., Ln are regular, there exists regular expressions r1, r2, . . ., rn such that L1 = L(r1), L2 = L(r2), . . ., Ln = L(rn). By definition, r1 + r2 + . . . + rn is the regular expression denoting L1 L2 . . . Ln. Thus, closure under finite union is immediate. • For LI , let L1 = L(M1), L2 = L(M2), . . ., Ln = L(Mn), where M1 = (Q1, , 1, q1,0, F1), M2 = (Q2, , 2, q2,0, F2), . . ., Mn = (Qn, , n, qn,0, Fn) are DFAs. We construct from M1, M2, . . ., Mn a combined automaton M = (Q, , , q0 = (q1,0, q2,0, . . . , qn,0), F), whose state set Q = Q1 ×Q2 ×. . .×Qn consists of tuples (q1,i1 , q2,i2 , . . . , qn,in ) whenever Mk is in state qk,ik , 1 k n. This is achieved by taking ((q1,i1 , q2,i2 , . . . , qn,in ), a) = (q1,j1 , q2,j2 , . . . , qn,jn ), whenever 1(q1,i1 , a) = q1,j1 , 2(q2,i2 , a) = q2,j2 , . . ., and n(qn,in , a) = qn,jn for all a . F is defined a s the set of all (q1,i1 , q2,i2 , . . . , qn,in ) such that q1,i1 F1, q2,i2 F2, . . ., and qn,in Fn. Now we have that w L1 L2 . . . Ln if and only if it is accepted by M. Consequently, LI is regular.