### Extended Transition Function

Remember that a transition function is a function that given a state and a symbol, returns to you a new state. An **extended transition function** $\delta ^*(s, w)$ is a function that takes a state $s$ and a string of symbols $w$, returns the new state after all those symbols are processed. This is also called a **multi-step transition function**.

## DFA Minimality

What is the minimum number of states a DFA needs to accept a given language? This question is important to defining DFAs. But to answer it, we need a few more definitions.

### Distinguishable Strings

Two strings $u$ and $v$ are **distinguishable** with respect to a language $A$ if there exists a string $w$ such that only one of $u.w$ and $v.w$ is in $A$.

For example, take the language $A = {w | w_2 = a}$. In this case, $\mathcal{E}$ and $a$ are distinguishable because $a.ab$ belongs to the set but $\mathcal{E}.ab$ does not(reminder that $\mathcal{E}$ represents the *empty string*). However, $a$ and $b$ are clearly indistinguishable because there exists no string for which a concatenation will have a different result.

Theorem: if $M$ accepts $A$ and strings $u$ and $v$ are distinguishable with respect to $A$, then $\delta^

(q_0, u) \neq \delta^(q_0, v)$. This can be easily proved by contradiction.

### Lower Bounds for Number of Automata States

Theorem: If $S = {w_1, w_2, … w_k}$ is a set of all $k$ pairwise distinguishable strings on $A$, then every DFA for $A$ must have at least $k$ states.

Taking the previous example of $A = {w | w_2 = a}$, you can see that there are four pairwise distinguishable strings. An example of this set is ${\mathcal{E}, x, xa, xb}$. Therefore, this state machine would need at least four states.