AFI to AFD determination

AFI to AFD

The Rabin-Scott theorem says that any language recognized by a automaton indeterministic finite can be recognized by a deterministic finite automaton (determination AFI to AFD). It is therefore possible to represent an indeterministic automaton by a deterministic automaton, this process is called determinization.

Consider for example thenon-deterministic finite automaton (K, T, M, I, F) following:
K = {S1, S2, S3, S4}
T = {a, b, c}
M = {(S1, a, S1), (S1, a, S3), (S2, b, S2), (S2, b, S3), (S3, c, S3), (S3, c, S4) }
I = {S1, S2}
F = {S4}
corresponding to graph next :

We then construct the states of the deterministic finite automaton (AFD) and their transition function. At the start, it has a single state which is composed of the set of initial states of the indeterministic finite automaton (AFI): in our example, the initial state of AFD is {S1, S2}.

Each time we add a new state in the AFD, we determine its transition function by making the union of the corresponding lines in the transition table of
AFI: on our example, for the state {S1, S2}, we make the union of the lines corresponding to S1 and S2, and we determine the transition function

In other words, when we are in state “S1 or S2 ″ and we read an a, we go to state“ S1 or S3 ″ (M ({S1, S2}, a) = {S1, S3 }), when we are in state “S1 or S2 ″ and read a b, we go to state“ S2 or S3 ″ (M ({S1, S2}, b) = {S2, S3 }) and when we are in state “S1 or S2 ″ and read a c, we go to the“ empty ”state, corresponding to the error state (M ({S1, S2}, c) = ∅.

The states {S1, S3} and {S2, S3} are then added to the AFD and their transition function is determined according to the same principle. Gradually, we build the following transition table for AFD:

The set of AFD states is K '= {{S1, S2}, {S1, S3}, {S2, S3}, {S3, S4}}. AFD states containing an AFI end state are end states. Here, AFI has a single final state S4 and the set of AFD final states is F '= {{S3, S4}}. This AFD corresponds to the following graph:

Another example

Here is another example of AFI to AFD determinization.

In practice, we only construct the states accessible from I, step by step: we start from the initial state I, then we calculate all the transitions that start from I, then we start again with the new states obtained, etc.

NB: the course method is also valid for the tutorials and the project. You use the one you understand best! You have the same example with the course notations after this method.

initial state: I = {1} transition by a: {1, 2} transition by b: {1}. We just did {1} so we're going to do {1,2}

state {1, 2} transition by a: {1, 2} transition by b: {1, 3}, we now do {1,3}

state {1, 3} transition by a: {1, 2} transition by b: {1}. There are no unvisited states left. Only state {1,3} contains a terminal state, {1,3} is therefore terminal.

Which gives us the following DFA:

The calculation by tables is much more readable.

Let's calculate the delta prime states:

The second line creates the state {1,3} for us. We notice that at the end, the automaton is the same as the one calculated with the previous method (state 3 is not useful since no one calls it).