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.