Determinize e-NFA to DFA

We want to show that the language recognized by an automaton with epsilon transitions can also be by a non-deterministic automaton without epsilon transitions. This operation will require the addition of new transitions.

Any language recognized by an NFA with ε-transitions can be recognized by an NFA (without ε-transitions) having the same number of states.

Construction of the NFA equivalent by extending δ in δ1 (the transitive closure is all the states that can be reached by a state by a given transition).

First step: Addition of ε-transitions by transitive closure.

For all the states q accessible from p by ε-transition (in several steps), we add a ε-transition directly from p to q. We thus extend the function δ: δ1 (p, ε) = all accessible states from p by ε-transition.

Second step: Adding additional transitions and additional initial states, then deleting the ε-transitions.

The initial states are all states accessible from the initial states by ε-transition.

For every transition from p to q by a letter, we add transitions from p to r with the
same letter for all ε-transitions from q to r: δ1(p, a) = δ(p, a) ∪ ( ∪q∈δ(p, a) δ1(q, ε)).

We delete all the ε-transitions

Example

The principle of the algorithm is to replace each path of length 1 starting with an epsilon-transition with a new transition that describes this path.

langage13

There are two path of length 1 that start with the transition on epsilon:

  • (1, ε, 3)(3, b, 3)
  •  (1, ε, 3)(3, c, 4)

Two new transitions are added to the automaton that summarize these two paths:

  • (1, b, 3)
  • (1, c, 4)

And we delete the transition (1, ε, 3).

langage14

The algorithm is a little more complex in cases where several epsilon-transitions follow each other and if they go into a final state, but the general principle presented here remains valid (just apply the first step).

The use of epsilon-transitions sometimes makes it possible to describe a language more legibly. It also makes it possible to simplify the description of certain operations (for example union or concatenation -> see Thompson automaton).

The existence of epsilon-transitions makes the automaton non-deterministic since it is always possible to borrow such a transition even when there is an ordinary transition that one could borrow.

Another example

Take the following automaton:

langage55

For this, we first have to calculate, for each state, the ε-successors of each state p, that is to say the set of states q such that there exists a path formed solely of ε-transitions starting of p arriving in q.

We calculate the ε-successors of each state: Succ ε (p) = {q, r}, Succ ε (q) = {r}, Succ ε (r) = ∅.

We obtain the following NFA:

langage56

You can then determine it with the NFA method to DFA, or determine it directly in its transitional form as the following example.

With transition table

Let’s take the automaton and transform it into a DFA:

langage55

The first step is to calculate the epsilon-closure for each state of this automaton:

Delta(Q) a b Closure-> Q’
p p {p,q,r}
q q {q,r}
r r {r}

For each state of the closure, we calculate its transitions in the alphabet without epsilon:

Delta(Q’) a b
{p,q,r} {p,r} {q}
{q,r} {r} {q}
{r} {r}

For each state obtained by the transitions, the closure is calculated:

Delta(Q’) a b
{p,q,r} {p,r} -> {p,q,r} {q} -> {q,r}
{q,r} {r} -> {r} {q} -> {q,r}
{r} {r} -> {r}

Let us denote {p, q, r} = P; {q, r} = Q and {r} = R. We obtain the following automaton:

langage58