How do you know the given DFA has the smallest number of states?

  • Often more than one DFA can be there that recognize the same language.

DFA Minimization Algorithm:

  1. Construct a table being indexed by non-final and final states.

Mark all non-final and final pairs (each pair does not have to be connected to one another; as long as they are non-final and final pairs).

  1. Process the first column (in this case, process q0).

In the column q0, look into which pairs have not been marked. Within each unarked pair, look to see if that one state will reach to another state depending on what edge it needs to traverse.

  1. Repeat this step with the other columns until you are sure if the states have reached a possible reachable state.
  2. Perform a second pass if needed.

DFA Minimization Algorithm Steps (Professor’s Words):

Given: A DFA M = (Q, ${\Sigma}$, ${\sigma}$, ${q_0}$, F)

  1. Create a 2D table of static pairs (p, q). All entries in the initiated table are not marked.
  2. Check all features (p,q) in the table and mark it if $p{\in}F$ and $p{\notin}F$ and vice versa.
  3. Repeat the following until an entire pass is made in the table and no new pair gets marked.
  • if (p, q) is marked and for a symbol ${a\in\Sigma}$ such that (${\sigma(p,a)}$, ${\sigma(q,a)}$) is marked then mark pair (p,q)
  1. After step 3, $p{\subset}q$ if entry (p,q) is not marked.
  2. Collapse all indistinguishable pair (${\approx}$) <- the symbol means equivalent

IMPORTANT: The time complexity of this algorithm is O(kn^2) where k is the number of alphabets and n is the number of states.

Reverse Language

Let L be an infinite/finite language, then the reverse of L will be denoted as:

  • ${L^r}$ = {${W^r}$ | ${W\in L}$}

Ex: ${L_1 = ab, aab, aaab, aaaab, …}$ ${L_1^R = ba, baa, baaa, baaaa, …}$

IMPORTANT NOTE: If L is a regular language, then L^R is also regular.

Proof:

  • Let M be a NFA accepting L.
  • To construct ${M^R}$, NFA accepting ${L^R}$ do as follows:
  1. If M has many final states, then introduce a new final state (call it foo). Connect final states of M to foo via ${\lambda}$-transition.
  2. Change start state to final state, then change final state (foo) as start state.
  3. Reverse the directions of arcs we obtain ${M^R}$.