Exercise 1.

We consider the alphabet $\Sigma$ = {a, b}. For each of the following languages over $\Sigma$ give an automaton (deterministic or not) that recognizes this language.

1. L₁ is the language consisting of all words w over $\Sigma$ such that w is not the empty word and none of the words aa, bb is a factor of w. Hint. It would be useful for the remaining questions to build a deterministic automaton of L₁.
2. $\overline{{L_1}}$ is the language consisting of all words w over $\Sigma$ such that w is the empty word or one of the words aa, bb is a factor of w.
3. L₁₂ is the language consisting of all words w over $\Sigma$ such that w is not the empty word and no words of the form aⁿ, bⁿ for n $\geq$ 3 is a factor of w.
4. L₂ is the language consisting of all words w over $\Sigma$ that belong to L₁₂ but not to L₁.

Answer 1