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

day one of theory of computation

 1. The Three Pillars of ToC 

• Automata Theory: Studying abstract mathematical models (machines) to understand how they process input.
• Computability Theory: Identifying which problems are "solvable" by a computer and which are "undecidable" (e.g., the Halting Problem).
• Complexity Theory: Measuring how efficiently a problem can be solved in terms of time (steps) and space (memory). 

2. Basic Definitions (The Vocabulary) 

To begin, you must master these fundamental building blocks: 

• Symbol: The smallest unit of data (e.g., 0, 1, a, b).
• Alphabet (
  

  $\Sigma$
  ): A finite, non-empty set of symbols (e.g., binary
  

  $\Sigma =\{0,1\}$
  ).
• String: A finite sequence of symbols from an alphabet (e.g., 0101).
• Language: A set of strings (e.g., the set of all binary strings that end in 1). 

3. Introduction to Finite Automata (FA) 

The first model usually introduced is the Finite State Machine, which has no external memory. 

• Deterministic Finite Automata (DFA): For every state and input symbol, there is exactly one transition to a next state.
• Non-Deterministic Finite Automata (NFA): Can have multiple possible next states for the same input, providing a more flexible but equivalent model for regular languages.