Exercise 3.

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.
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.

Answer 3