2-25-2025 - FSMs

Finite State Automata

Which direction? Finite State Machine → Push-down state machine (automaton) → Turing Machine

regular expressions: finite state machine

Regular expressions: history-less finite state machine (pumping lemma)

RE ⇐> FSM

Given some state of the universe, calculate where I go to next memory is in the states

$$FSM=\{\Sigma ,Q,q_0,F,\delta \}$$

• $\Sigma$ is the alphabet, or symbols allowed
• $Q$ is the set if states in the graph
• $q_0$ is the starting state; $q_0\in Q$
• $F$ is accepting/yes states; $F\subseteq Q$
• $\delta$ = [transitions]: src, sym, dest
  • src, dest $\in Q$
  • sym $\in \Sigma$