Summary

• DFA’s, NFA’s, and ε–NFA’s all accept exactly the same set of languages: the regular languages.
• The NFA types are easier to design and may have exponentially fewer states than a DFA.
• But only a DFA can be implemented!

1. What is a Finite Automaton

• A formal system.
  • ⇒ 无二义性，准确描述的
• Remembers only a finite amount of information.
• Information represented by its state.
  • ⇒ a global snapshot
• State changes in response to inputs.
• Rules that tell how the state changes in response to inputs are called transitions.

2. Importance of Finite Automata

• Used for both design and verification of circuits and communication protocols.
• Used for many text-processing applications.
• An important component of compilers.
• Describes simple patterns of events, etc.

3. Accptance of Inputs

• Given a sequence of inputs (input string), start in the start state and follow the transition from each symbol in turn.
• Input is accepted if you wind up in a final (accepting) state after all inputs have been read.
• Final states can also have successors