Automata Equivalence: Automata without epsilon transitions, inaccessible and useless states

Description

This post aims to demonstrate a way to get the Deterministic Finite Automata (DFA) without ε (epsilon) transitions, inaccessible and useless states, and equivalent to automaton in the cover.

The alphabet of automaton is {a, b, ε}, q0 is the initial state, q3 and q6 are final states, and the ε transitions allow the automaton to change its state, without using an input symbol.

The first step is to put the automaton in tabular notation or transition table, as shown below. The rightwards arrow (→) indicates initial states, the leftwards arrow (←) indicates final states and the left right arrow (↔) indicates that state are both initial and final.

For example, the state q0 has transition to both q1 and q4 through ε. The state q5 has transition to himself through a, and to q6 through symbol ε.

Eliminating ε Transitions

Now, it’s necessary to analyze each state and merge it with each state reached by an ε transition, until the analyzed state does not have any ε transition.

As seen above, the first merge (analyzed state q0 and {q0, q4}) achieves transitions to states q1, q4and {q2, q5} through a, b and ε, respectively. The second merge tries to eliminate the new ε transitions {q2, q5} but results in a new ε transitions {q3, q6}. The third merge eliminates the ε transition, where now state q0 is also a final state (←), because merges with a final state q6, besides has transitions to {q1, q3, q5} and {q2, q4, q6} through a and b, respectively.

After analyzing all the states, we have the following transition table as result:

Non-Determinism

The next step is to remove the non-determinism from the automaton. The non-determinism can be indicated by q0 transitions (table above), for example, when receiving a, three moves can be performed (for q1, q3, and q5). Thus, it is necessary to remove the non-determinism so that when receiving an input, the automaton has only one possible path to follow.

For this, each set of transitions ({q1, q3, q5}) will be marked as a new state (q1q3q5) and the transitions of this new state will be given by the merge of the sets of states that form this new state, and if one of these states of the set is final, this new state will also be. If non-determinism continues, that is, a new set of transitions appears that is not yet a new state, the process will continue. The table below shows the result of removing non-determinism.

Accessible and Useless States

The next steps check if the states are accessible and then if they are useless. To check if the state is accessible, the analysis starts with the initial state q0 (initially accessible, marked as ok in the accessible field), and we check which states are accessible through this (q1q3q5e q2q4q6) and mark them as accessible and finish the analysis of q0 by marking as considered. Then we continue to analyze the states marked as accessible but not yet considered until we find all the accessible ones and all those accessible ones are analyzed (marked as ok in the considered field).

The analysis of useless states only considers accessible states. However, now we start analyzing by one of the final states (marked as useful), for example, q3q5, then we check which states reach this, in this case only q6 (marked as useful), and we mark q3q5as considered. The process continues with q6 but is not accessible by anyone other than itself, and we mark it as considered. We then check if there is another final state, the process continues until there is no other final state. In the end, we find that all accessible states are useful, so no changes are made. After both analyses, the states q1, q2, q4, q5, q1q3, and q4q6 are removed.

Renaming the states as follows:

q1q3q5 = q1
q2q4q6 = q2
q2q6 = q3
q3q5 = q4
q3 = q5
q6 = q6

We obtain the tabular form of the automaton without ε transitions, inaccessible and useless states and equivalent to the initial automaton:

Final Automaton

Converting from tabular notation (above) to automaton in state representation we get:

This automaton recognizes the following language:

L = a*b*a* +  b*a*b*

This language is the same recognized by the initial automaton.

Here a way to obtain an equivalent finite deterministic automata without ε transitions, inaccessible and useless states was presented. Share if it’s helpful for you.