Unless stated otherwise, the base alphabet in this problem set is = {a,b}.

(s is being add to the alphabet along with the a,b)

4. Give an FA (DFA or NFA) that accepts { w | w ends with an odd number of bs}.[1]

5. Specify (in English) an algorithm that takes a DFA (as a graph or a table, your choice) and checks whether the language of the DFA is finite [1]

3. Give a DFA () for the language D: & is in D if sis in D, then both saa and sbb are also in D [1/2]