Suppose there always exist pairs of finite automata that recognize L and the complement of L, respectively. What does this imply? Suppose there always exist pairs of finite automata that recognize L and the complement of L, respectively. What does this imply? **my answer** That all languages can be recognized by finite automata. This was a multiple choice question and i feel that I am right based on the supposition that we are making. It seems trivial to me but I am told this is not true.

**Hint**. Regular languages are closed under complementation.

EDIT. A language is regular if and only if it is recognized by a finite automaton. Now, knowing that there exist pairs of finite automata that recognize a language and its complement, respectively, just means that the language is regular. It is certainly not true that all languages are recognized by a finite automaton, even on a one-letter alphabet. For instance, the language $\\{a^{n^2} \mid n \geqslant 0 \\}$ is not regular.