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.