For each of the following languages construct a deterministic finite automaton that recognizes it. In any case show the state diagram of the automaton (only).

(a) { w {a,b,c}* | w does not contain two consecutive identical letters } (b) { w {a,b}* | w ends in a and contains at most one pair of consecutive b }

(c) { w {a,b}* | there exist x,y{a,b}* such that w=xy, where x does not contain the string aba and y starts with bb }

For example, the word abbaba belongs to the language since we can set x=a, y = bbaba while the word ababb does not belong to the language since it is impossible to break the word into two parts as the language description predicts.

(d) {w{a,b}*||w|_a mod 3=1 or |w|_b mod 4=2}

Note: For word w and symbol x we write |w|x for the number of occurrences of x

in w. For example |abbaabb|_a = 3 and |bbbb|_a = 0.