Question: Use Exercise to show that the language consisting of all bit strings that are palindromes (that is, strings that equal their own reversals) is not regular.
Exercise: Suppose that L is a subset of I ∗ and for some positive integer n there are n strings in I ∗ such that every two of these strings are distinguishable with respect to L. Prove that every deterministic finite-state automaton recognizing L has at least n states.