Transformation from non-deterministic finite automaton to deterministic finite automaton

Transformation from finite non-deterministic automaton to finite deterministic automaton . Any strict AFND , that is an AFND that is not AFND-V , can be transformed to AFD using an algorithm that transforms the states of the AFND into new states that are subsets of the original states and applies the closure to them to confirm the connection between each of the components and thus eliminate indeterminism.

Although this algorithm always obtains an equivalent AFD, it cannot be said that it is the minimal version of it, for this, other transformations must be applied.

Summary

[ hide ]

  • 1 Algorithm
  • 2 Example
  • 3 Consequences
  • 4 See also
  • 5 Sources

Algorithm

Let be a strictly non-deterministic finite automaton ( AFND ) defined by the 5-tuple A = <Q, T, g, F, q 0 > , where Q is the set of states, T the terminal symbol alphabet , the relation of transitions or (read: from state i through terminal x goes to j ), F are the final or arrival states within Q , 0 is the initial or starting state

  1. Abecomes AFD = <Q A , T, g A , F A , q 0A > ‘ , such that:
    1. A= P (V) – {{}} , with P (V) is the power set of the vertices of A .
    2. A= {x | } .
    3. A= {<r, x, q> | } .
    4. 0A= {q 0 } .
  2. Then all states and their corresponding unreachable transitions from the initial state 0Aare removed from AFD .

Example

See the transformation process from AFND to AFD of controller A = <{q0, q1, f}, {a, b}, {<q0, a, q0>, <q0, b, q0>, <q0, a, q1>, <q1, b, f>}, {f}, q0> , which recognizes strings of a s and b s that begin with any number of these letters and end forcibly in ab . The following may be your state diagram :

First, a derived automaton AFD = <V AFD , T AFD , g AFD , F AFD , {q0}> is obtained from the power set of the states of A where:

  • AFD= {{q0}, {q1}, {f}, {q0, q1}, {q0, f}, {q1, f}, {q0, q1, f}} .
  • AFD= {a, b} .
  • AFD= {{f}, {q0, f}, {q1, f}, {q0, q1, f}} .

Whose diagram would be:

Inaccessible states are then removed {q1} , {f} , {q1, f} , {q0, q1, f} , determined by the closing of {q0} , and is:

  • AFD= {{q0, {q0, q1}, {q0, f}}, {a, b}, {<{q0}, b, {q0}>, <{q0}, a, {q0, q1 }>, <{q0, q1}, a, {q0, q1}>, <{q0, q1}, b, {q0, f}>, <{q0, f}, a, {q0, q1}> , <{q0, f}, b, {q0}>}, {{q0, f}}, {q0}} .

Consequences

The existence of this method allows the conversion of any AFND to an equivalent AFD, that is, the elimination of strict indeterminism (the same terminal symbol leads to more than one state from a common origin), although it does not guarantee that it is the minimal equivalent AFD. For this, other steps to reduce the AF must be followed.

Another situation could occur in the case that you want, for example, from a regular expression you want to obtain your deterministic finite automaton , using the Thompson algorithm you obtain the AFND-V , then proceed by the closing method- xi to its conversion to AFND and then the transformation to AFD can be applied to the automaton.

 

Leave a Comment