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

1. Tricky: The language L = {w | w contains as many occurrences of the substring ab as occurrences of the substring ba} is regular. Prove it by giving an FA (deterministic or non-deterministic) for L. Explain why this FA accepts this language. [1] Examples:

• accepted: aba, baaabab
• not accepted: abb, abababab

2. Give a DFA for all strings that have an even number of as and an odd number of bs. []