Automata Equivalence: Automata without epsilon transitions, inaccessible and useless states
Tags: computerscience
Published: 2022-04-24 20:02:54

## 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.

![Tabular notation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aae9fljrnnaj5cn09cqg.png)

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.


![Elimination of ε transitions of q0](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/72b48uj48rwbhpccz1yj.png)

As seen above, the first merge (analyzed state `q0` and {q0, q4}) achieves transitions to states `q1`, `q4 `and {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:


![Transition table without ε transitions](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sdcdxuqg7gwrpn2ke1on.png)

## 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.


![Deterministic automaton and analysis of accessible and useless states](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ftf45muscsljooehlg41.png)

## 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 transition table](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g8dgil6t6dk79w26jbo9.png)

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


![Final automaton](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/akl4g7j4faoi3tkrsmwg.png)

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.