／var／logmarcus chiu

Finite-State Automaton／Machine (FSA／FSM)

Created on

Finite-State Automaton (FSA) or Finite State Machine (FSM) or Finite-State Automata or Finite Automata or Automaton

FSM Parameters

  • Q - a finite set of states
  • Σ - a finite set of input symbols
  • q - the start state
  • F - a finite set of final states
  • ẟ(q, i) - a transition function or transition matrix between states. given a state q in Q and input i in Σ, ẟ(q, i) returns a new state q’ in Q. thus, ẟ is a relation from Q x Σ to Q

FSM - Types (Deterministic vs Non-Deterministic)

  • Deterministic FSA (DFSA) - algorithm have exactly 1 choice for every input
  • Non-Deterministic FSA (NFSA) - algorithm have more than 1 choice for at least 1 input
    • epsilon-transition or ϵ-transition - automaton may transition without input
Deterministic FSA

Non-Deterministic FSA (multiple choices for input a)

Non-Deterministic FSA (ϵ-transition)

Problem with NFSA

the problem with Non-Deterministic FSM is figuring out which choice to make when there are multiple choices

3 Standard Solutions:
  • backup - whenever choice point reached, we put a marker at input and state the automaton was in. then if it turns out we took the wrong choice, we backup and try another path
  • look ahead - look ahead in the input sequence to help us decide which path to take at choice point
  • parallelism - whenever choice point reached,  proceed with every alternative path in parallel

Relation of DFSA and NFSA

for any NFSA there is an equivalent DFSA

there is a simple algorithm for converting NFSA to DFSA, although the number of states in this equivalent DFSA may be much larger