CS 341 Homework 9Languages That Are and Are Not Regular1. Show that the following are not regular.(a) L = {wwR : w {a, b}*}(b) L = {ww : w {a, b}*}(c) L = {ww' : w {a, b}*}, where w' stands for w with each occurrence of a replaced by b, and vice versa.2. Show that each of the following is or is not a regular language. The decimal notation for a number is thenumber written in the usual way, as a string over the alphabet {-, 0, 1, …, 9}. For example, the decimal notationfor 13 is a string of length 2. In unary notation, only the symbol 1 is used; thus 5 would be represented as 11111in unary notation.(a) L = {w : w is the unary notation for a natural number that is a multiple of 7}(b) L = {w : w is the decimal notation for a natural number that is a multiple of 7}(c) L = {w : w is the unary notation for a natural number n such that there exists a pair p and q of twin primes,both > n.} Two numbers p and q are a pair of twin primes iff q = p + 2 and both p and q are prime. For example,(3, 5) is a pair of twin primes.(d) L = {w : w is, for some n 1, the unary notation for 10n}(e) L = {w : w is, for some n 1, the decimal notation for 10n}(f) L = {w is of the form x#y, where x, y {1}+ and y = x+1 when x and y are interpreted as unary numbers}(For example, 11#111 and 1111#11111 L, while 11#11, 1#111, and 1111 L.)(g) L = {anbj: |n – j| = 2}(h) L = {uwwRv : u, v, w {a, b}+}(i) L = {w {a, b}* : for each prefix x of w, #a(x) #b(x)}3. Are the following statements true or false? Explain your answer in each case. (In each case, a fixed alphabet is assumed.)(a) Every subset of a regular language is regular.(b) Let L = L1 L2. If L is regular and L2 is regular, L1 must be regular.(c) If L is regular, then so is L = {xy : x L and y L}.(d) {w : w = wR} is regular.(e) If L is a regular language, then so is L = {w : w L and wR L}.(f) If C is any set of regular languages, C (the union of all the elements of C) is a regular language.(g) L = {xyxR : x, y *} is regular.(h) If L = L1 L2 is a regular language and L1 is a regular language, then L2 is a regular language.(i) Every regular language has a regular proper subset.(j) If L1 and L2 are nonregular languages, then L1 L2 is also not regular.4. Show that the language L = {anbm : n m} is not regular.5. Prove or disprove the following statement: If L1 and L2 are not regular languages, then L1 L2 is not regular.6. Show that the language L = {x {a, b}* : x = anbambamax(m,n)} is not regular.7. Show that the language L = {x {a, b}* : x contains exactly two more b's than a's} is not regular.8. Show that the language L = {x {a, b}* : x contains twice as many a's as b's} is not regular.9. Let L = {w : #a(w) = #b(w)}. ( #a(w) = the number of a’s in w.)(a) Is L regular?Homework 9 Languages That Are and Are Not Regular 1(b) Is L* regular?Solutions 1. (a) L = {wwR : w {a, b}*}. L is the set of all strings whose first half is equal to the reverse of the second half. All strings in L must have even length. If L is regular, then the pumping lemma tells us that N 1, such that strings w L, where |w| N, x, y, z, such that w = xyz, |xy| N, y , and q 0, xyqz is in L. We must pick a string w L and show that it does not meet these requirements.First, don’t get confused by the fact that we must pick a string w, yet we are looking for strings of the form wwR. These are two independent uses of the variable name w. It just happens that the problem statement uses the same variable name that the pumping lemma does. If it helps, restate the problem as L = {ssR : s {a, b}*}.We need to choose a “long” w, i.e., one whose length is greater than N. But it may be easier if we choose one thatis even longer than that. Remember that the fact that |xy| N guarantees that y (the pumpable region) must occurwithin the first N characters of w. If we don’t want to have to consider a lot of different possibilities for what y could be, it will help to choose a w with a long first region. Let’s let w = aNbbaN. We know that y must consist ofone or more a’s in the region before the b’s. Clearly if we pump in any extra a’s, we will no longer have a string in L. Thus we know that L is not regular.Notice that we could have skipped the b’s altogether and chosen w = aNaN. Again, we’d know that y must be a string of one or more a’s. Unfortunately, if y is of even length (and it could be: remember we don’t get to pick y), then we can pump in all the copies of y we want and still have a string in L. Sure, the boundary between the first half and the second half will move, that that doesn’t matter. It is usually good to choose a string with a long, uniform first region followed by a definitive boundary between it and succeeding regions so that when you pump, it’s clearly the first region that has changed. (b) L = {ww : w {a, b}*}. We’ll use the pumping lemma. Again, don’t get confused by the use of thevariable w both to define L and as the name for the string we will choose to pump on. As is always the case, theonly real work we have to do is to choose an appropriate string w. We need one that is long enough (i.e., |w| N).And we need one with firm boundaries between regions. So let’s choose w = aNbaNb. Since |xy| N, we knowthat y must occur in the first a region. Clearly if we pump in any additional a’s, the two halves of w will nolonger be equal. Q. E. D. By the way, we could have chosen other strings for w. For example, let w = baNbaN.But then there are additional choices for what y could be (since y could include the initial b) and we would have towork through them all. (c) L …
View Full Document
Unlocking...