1 Give regular expressions for the following languages a w a

1. Give regular expressions for the following languages:

(a) {w {a,b} | w has an even number of b’s}

(b) {w {a,b} | w does not contain the substring ab}

(c) {w {a,b} | w contains substring ab an even number of times}

(d) {w {a,b} | w has an even number of a’s and even number of b’s} To help the grader out (and to increase chance of partial credit), if you have a long regular expression, please identify small conceptual parts and explain what each part does.

2. You probably know the trick that a number is a multiple of 9 if and only if the sum of its decimal digits is a multiple of 9. Here is a similar trick for multiples of 3 in binary. Prove that a number is a multiple of 3 if and only if writing that number backwards in binary is also a multiple of 3. Example: 0011bin = 3dec is a multiple of 3, and so is 1100bin = 12dec. However, 100101bin = 37dec is not a multiple of 3, and neither is 101001bin = 41dec. Hint: First transform this to a statement about regular languages over alphabet {0,1}.

3. If A is a language over alphabet , dene: undouble(A) def = {w | ww A}. Show that if A is regular, then so is undouble(A). Example: if A = {,0,11,0010,0101} then undouble(A) = {,1,01}. Warmup / partial credit: Suppose M = (Q,,,s,F ) is a DFA for A. Show that the following language over alphabet Q is regular: {qw | q Q and w and (s,w) = q and (q,w) F } Just to be clear, strings in this language (for the warm-up question only) consist of one character from Q and then any number of characters from .

Solution

1. Give regular expressions for the following languages:

(a) {w {a,b} | w has an even number of b’s}

a*(ba*ba*)*

(b) {w {a,b} | w does not contain the substring ab}

b*a*

(c) {w {a,b} | w contains substring ab an even number of times}

ab*(ab*)*

(d) {w {a,b} | w has an even number of a’s and even number of b’s}

even number of b\'s = (a*ba*ba*)*

even number of a\'s=(b*ab*ab*)*