Question: Let Ln be the set of strings with at least n bits in which the nth symbol from the end is a 0. Use Exercise to show that a deterministic finite-state machine recognizing Ln must have at least 2n states.
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(DFSA) recognizing L has at least n states.