Designing a Finite State Automaton
Read this discussion of hints on designing a finite state automaton to recognize a given regular set.
Not all languages are regular. Because a finite state machine has a finite number of states, it can only remember a finite number of inputs. Consider the set {on 1n for all n >= 0}. Because this set requires a recognizing machine to remember n 0's for any n (so that it can then look for n 1's), the number of states is infinite, i.e. not a finite state machine. Thus, the language is not regular. Hence, one way to show that a language is not regular is to show that the automaton that recognizes it has an infinite number of states.