CS202: Discrete Structures

9.2: Finite State Automata

• Finite State Automata URL

  Read this discussion on finite state automata.

• 9.2.1: Automaton and Accepted Language

  • Automaton and Accepted Language URL

    Read this discussion of regular sets and their acceptance by finite state automata.
    

• 9.2.2: Designing a Finite State Automaton

  • Designing a Finite State Automaton URL

    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 {o_n 1_n 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. 
    

• 9.2.3: Simplifying Finite State Automata

  • Simplifying Finite State Automata URL

    Read this discussion of ways to simplify finite state automata.