Day three of theory of computation

 1. Non-deterministic Finite Automata (NFA) 

Unlike a DFA, an NFA allows a machine to explore multiple paths simultaneously. 

• Definition: For a given state and input symbol, an NFA can transition to zero, one, or multiple states.
• Acceptance: A string is accepted if at least one possible path leads to a final state.
• Flexibility: NFAs are generally easier to construct than DFAs because you don't need to define transitions for every possible input or worry about "dead states". 

2. NFA with Epsilon Transitions (

$ϵ$

-NFA) 

An

$ϵ$

-NFA introduces the epsilon (

$ϵ$

) move, which allows the machine to change states without consuming any input symbol. 

• 

  $ϵ$
  -Closure: This is a critical Day Three concept. It is the set of all states reachable from a specific state using only
  

  $ϵ$
  transitions (including the state itself).
• Use Case:
  

  $ϵ$
  -NFAs are highly useful for combining smaller machines (e.g., when implementing the "union" or "star" operations in Regular Expressions). 

3. Equivalence of NFA and DFA (Subset Construction) 

The most important takeaway of Day Three is that NFAs and DFAs are equally powerful; they both recognize the same class of languages (Regular Languages). 

• Conversion: Any NFA can be converted to an equivalent DFA using the Subset Construction (or Powerset Construction) algorithm.
• State Explosion: While an NFA with
  

  $n$
  states is simpler, its equivalent DFA may have up to
  

  $2^n$
  states in the worst case.

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'.