I. Definition

1. Alphabets, Strings & Languages

• An alphabet is any finite set of symbols.
  • Binary alphabet: $\{0, 1\}$
  • Set of signals used by a protocol
• A string over an alphabet $Σ$ is a list, each element of which is a member of $Σ$.
  • Strings shown with no commas or quotes, e.g., $abc$ or $01101$.
  • $Σ^*$ = set of all strings over alphabet $Σ$.
  • The length of a string is its number of positions.
  • ε stands for the empty string (string of length 0).
• A language is a subset of $Σ^*$ for some alphabet $Σ$.

2. Formalism

$$ A = (Q,\Sigma, δ,q_0,F ) $$

A formalism for defining languages, consisting of:

1. A finite set of states (Q, typically).
2. An input alphabet (Σ, typically).
3. A transition function (δ, typically).
4. A start state ($q_0$, in Q, typically).
5. A set of final states (F ⊆ Q, typically).
   • “Final” and “accepting” are synonyms

3. The Transition Function

$$ δ(q, a) $$

• Takes two arguments: a state and an input symbol.
• Means the state that the DFA goes to when it is in state $q$ and input $a$ is received.

Note: The strict definition is that $δ$ is a total function: always a next state – add a dead state if no transition.

II. Graph Representation of DFA