CS 481 Automata, Winter 1998, HW #1
Due: 21 January, 1997 (Wednesday)


Write regular expressions AND construct DFA's for the following languages
over the alphabet {a,b}.

L1 = {}
L2 = {ab,abb,abbb}
L3 = { w | w has at least one a and at least one b}
L4 = { w | the number of b's in w is divisible by 3}
L5 = { w | w has different first and last symbols}
L6 = { w | w does not end with ba}

FOR GRADUATE CREDIT:

L = { w | length of w is odd}
L = { w | length of w is even and w ends with an a}
L = { w | length of w is even and w ends with an a and 
          every even position letter is an a}