Finite State Automata

• Consist of a finite number of states and transitions
• Transitions are labelled with input characters.
• There is one start state .
• A subset of the states are called final states .
• A finite state automaton starts in the start state, and for each input symbol follows an edge labelled with that symbol.
• It accepts an input string iff it ends up in a final state.
• Examples: Blackboard.