4.1 Finite state machines

• A finite state machine is a mathematical model of computation with a finite number of states
• States in a finite state machine represent possible configurations or situations the machine can be in.
• Transitions in a finite state machine represent changes from one state to another based on the input received
• The input alphabet of a finite state machine is the set of symbols it can process.
• The output alphabet of a finite state machine is the set of symbols it can emit
• What is the input alphabet for a light switch FSM with states On and Off?

  {flip}
• What is the output alphabet for a light switch FSM with states On and Off?

  {On, Off}
• Order the transitions of a light switch FSM based on input and current state:

  1️⃣ Input: flip, Current State: Off, Next State: On, Output: On

  2️⃣ Input: flip, Current State: On, Next State: Off, Output: Off
• In the state diagram of a light switch FSM, the transition from Off to On is labeled with the input symbol flip
• Match the FSM component with its description:

  States ↔️ Finite number of configurations

  Transitions ↔️ Changes between states

  Input Alphabet ↔️ Set of symbols processed

  Output Alphabet ↔️ Set of symbols emitted
• What output does the light switch FSM emit when it transitions from Off to On upon receiving flip input?

  On
• In a deterministic finite automaton (DFA), each state has exactly one transition for each input symbol.
• A deterministic finite automaton (DFA) is easy to implement and analyze
• What is an example of a device that can be modeled using a DFA?

  Simple vending machine
• In a non-deterministic finite automaton (NFA), states can have multiple transitions for the same input symbol.
• A non-deterministic finite automaton (NFA) is more flexible but harder to analyze
• What is an example of a pattern that an NFA can accept that a DFA cannot?

  "abc" or "abd"
• Non-deterministic Finite Automata (NFAs) allow states to have multiple transitions for the same input symbol
• Non-deterministic Finite Automata (NFAs) are easier to implement and analyze compared to DFAs.

  False
• What does DFA stand for in the context of finite state machines?

  Deterministic Finite Automaton
• In a DFA, each state has exactly one transition for each input symbol
• Deterministic Finite Automata (DFAs) are harder to implement and analyze than NFAs.

  False
• What does NFA stand for in the context of finite state machines?

  Non-Deterministic Finite Automaton
• NFAs can have states with multiple transitions for the same input symbol.
• What is the acceptance criteria for NFAs?

  At least one path to accept
• Steps to construct a state transition diagram

  1️⃣ Identify the states

  2️⃣ Define the input alphabet

  3️⃣ Draw states as circles

  4️⃣ Indicate the start state

  5️⃣ Draw transitions as arrows

  6️⃣ Mark accepting states
• What are the two states in the light switch example of a state transition diagram?

  On and Off
• The input alphabet for the light switch example is flip
• A finite state machine with states {Off, On} and input alphabet {flip} has a state transition diagram
• In a light switch FSM, if the current state is Off and the input is 'flip', the next state is On.
• To construct a state transition diagram, one must identify the states, transitions, and input symbols
• Steps to construct a state transition diagram

  1️⃣ List all possible states

  2️⃣ Identify the input alphabet

  3️⃣ Define the transitions between states

  4️⃣ Represent the information using a diagram or table
• For a light switch FSM, the input alphabet is {flip}.
• What is the output alphabet for a light switch FSM with states {Off, On}?

  {On, Off}
• A finite state machine is a mathematical model of computation consisting of states, transitions, and potentially output symbols
• The input alphabet of an FSM is the set of symbols it can process.
• Match the components of an FSM with their descriptions:

  States ↔️ Possible configurations of the machine

  Transitions ↔️ Changes between states based on input

  Input Alphabet ↔️ Set of symbols the FSM processes

  Output Alphabet ↔️ Set of symbols emitted during transitions
• A finite state machine consists of states, transitions, input alphabet, and output alphabet
• The states of an FSM represent the finite number of configurations the machine can be in.
• What does the input alphabet of an FSM represent?

  Symbols the FSM processes