CIS 2620 Notes 2.1

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 ^\ast (q_0, u) \neq \delta ^\ast (q_0, v)$.

This property 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.