day two of theory of computation

 1. The Formal Definition (The 5-Tuple) 

A DFA is mathematically defined as a 5-tuple

$M=(Q,\Sigma ,\delta ,q_0,F)$

: 

• 

  $Q$
  : A finite set of states (e.g.,
  

  $\{q_0,q_1,q_2\}$
  ).
• 

  $\Sigma$
  : A finite set of symbols called the alphabet (e.g.,
  

  $\{0,1\}$
  ).
• 

  $\delta$
  : The transition function, defined as
  

  $\delta :Q\times \Sigma \to Q$
  . This ensures that for every state and input, there is exactly one destination state.
• 

  $q_0$
  : The start state (
  

  $q_0\in Q$
  ).
• 

  $F$
  : The set of accept states or final states (
  

  $F\subseteq Q$
  ). 

2. Key Rules of DFA Design 

• Determinism: Every state must have exactly one outgoing arrow for every symbol in the alphabet.
• No Epsilon (
  

  $ϵ$
  ) Moves: A DFA cannot change states without consuming an input symbol.
• Completeness: If a state should not lead to an acceptance path, it must transition to a "Dead State" (trap state) where it stays for all subsequent inputs. 

3. Practical Design Examples 

Common Day Two exercises include building machines for specific languages: 

• Strings ending with '01': Requires at least 3 states to track the last two seen characters.
• Even number of 'a's: Uses two states to flip-flop between "Even" (Accepting) and "Odd" (Non-Accepting) counts.
• Strings starting with 'ab': Uses a "Dead State" for any string that begins with 'b' or 'aa'.