THEORY OF
COMPUTATION
MTE PROJECT (CO303)
WRITING A PROGRAM FOR CONVERSION OF
NFA TO DFA.
Introduction
The objective of the project is to develop an algorithm to convert a Non-Deterministic Finite
Automata (NFA) to a Deterministic Finite Automata (DFA).
The conversion process will never fail because if a language can be recognized by an NFA, there
will always be an equivalent DFA. Because our procedure should be able to handle a NFA
containing -productions (i.e. null-productions or λ productions), the final DFA should have the
ability to contain multiple states within a single state.
In addition, a trap state will also be included in the resulting DFA if any state in the given NFA has
an undefined transition.
Finite Automata
Finite automata are used to recognize patterns.
It takes the string of symbol as input and changes its state accordingly. When the desired symbol
is found, then the transition occurs.
A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F), where:
◦ Q: finite set of states
◦ ∑: finite set of the input symbol
◦ q0: initial state
◦ F: final state
◦ δ: Transition function
Graphical Representation
1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by a double circle
Deterministic Finite Automata
A DFA is a collection of 5-tuples same as that of FA. Deterministic refers to the uniqueness of the
computation.
The finite automata are called deterministic finite automata if the machine is read an input
string one symbol at a time.
In DFA, there is only one path for specific input from the current state to the next state.
DFA does not accept the null move, i.e., the DFA cannot change state without any input
character.
DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.
Its Transition function can be defined as : “δ: Q x ∑→Q”
Non-Deterministic Finite Automata
NFA stands for non-deterministic finite automata. It is easy to construct an NFA than DFA for a
given regular language.
The finite automata are called NFA when there exist many paths for specific input from the
current state to the next state.
Every NFA is not DFA, but each NFA can be translated into DFA.
NFA is defined in the same way as DFA but with the following two exceptions, it contains
multiple next states, and it contains ε transition.
Its Transition function can be defined as : “δ: Q x ∑ →2Q ”
Differences between NFA and DFA
An NFA is similar to a DFA, except that there are three main differences that are allowed in a NFA
but not allowed in a DFA:
1) NFA permits -transitions
2) NFA is able to have undeclared or undefined transitions
3) NFA may contain transitions to different states after receiving a single input (can be in
multiple states at once)
Factors during conversion
During the process, there are important factors that the algorithm should track during the
conversion process:
1) Is a trap state required?
2) What is the initial state?
3) What are the final states?
4) Does the original NFA contain -transitions?
5) How will the algorithm know when it is done?
6) Is there a -transition from initial state to final state?
Methodology
The implementation of the NFA-to-DFA algorithm was developed using Javascript. The basic
concept was that users would be able to input an NFA in a web interface (HTML) and then the
site, using Javascript, would convert the NFA provided to an equivalent DFA. The algorithm itself
does not rely on any third-party libraries; however, Viz.js was used for the purpose visualizing
finite automatas.
Automata format
An NFA and DFA both use the same data structure internally as that a DFA is also an NFA, but an
NFA is not a DFA. This data structure used to represent an NFA/DFA is simply a class named NFA.
The data structure follows the formal definition of an NFA. The formal definition states that the
NFA is set of 5 tuples same as FA.
User Input
The user input was designed in such a way
that would be the most intuitive for the end
user. To achieve this, the HTML page was
made to be clutter-free and to only prompt
the user for necessary input values. For
example, the algorithm would automatically
generate the alphabet set from the
transitions provided by the user instead of
prompting the user to define the alphabet
set. By looking at user input form, it can be
pointed out that the most prominent aspect
are the textboxes acting as placeholders for
user inputs.
NFA to DFA conversion
After the user enters the information, the NFA is created and displayed to the user so that they can
confirm the input. Then, the first state of the DFA is created by calculating the closure of the initial state
in the NFA.
The initial state of the DFA is stored in a stack. When the algorithm creates a new state, that new state
will be added to the stack for further processing. While the stack is not empty, the algorithm will check
all outgoing transitions for the current state and then check to see if a new state is created from these
transitions based on its closure.
The new transitions for the DFA are created by the union operation with the closure of the transitions
from the original NFA for the current state in the DFA. If a new state is created, it is added to the stack. If
the new transition is empty, a trap state is created instead.
A trap state is simply a state that only contains transitions to itself. Because of this, once the automata
enters the trap state in a DFA, there is no way out of that state. The reason a trap state is required in
some cases is because a DFA requires a transition for every possible input in the alphabet for every state
unlike an NFA.
NFA to DFA conversion Algorithm
When creating a new state and its transitions, it is
critical to check the original NFA and search for its
original states, their transitions, and closure.
A stack was used along with a loop to keep track of
newly generated states in the DFA. As a result, all states
in the DFA would be considered and populated with
their proper transitions.
The loop terminates when the stack becomes empty
because all of the new states would have been created.
Generally, it did not matter what order the data
structure processed elements in.
The stack was used was because of its simplicity;
Reduction
DFA reduction was not necessary for this project. Regardless, a DFA minimization algorithm was
implemented as a bonus and as a way to have cleaner results. The minimization works as
followed: after the DFA is created, the code calls the reduction function. This function goes
through all the states of the DFA and searches for two states which have the same transitions for
every possible s 2 and that are final or nonfinal, i.e., if one state is final, the other one must also
be final for them to be considered equal. If the states are equal, the algorithm then decides
which state should be removed. If one state is the initial state, that means that this state should
not be removed and, instead, the other state should be removed. After the algorithm decided
which state to remove, the code then searches for all the instances of that state in the DFA and
replaces it with the other equivalent state.
Reduction Algorithm
When the original NFA is generated and every time a new
state for the DFA is created, the program will save its
current state and make its display viewable by the user.
That way, the user can select each step of the conversion
process to see how the algorithm generated the final DFA.
In addition, the HTML page will also render the original NFA
so that the user can confirm their input. The Viz.js library
uses the dot graph format to serialize and deserialize finite
automata's. An example serialization in the dot text format
is shown in the first Listing.
Results:
Insert user input
Results:
Steps show here
Results:
Tests:
Multiple NFAs were used to test this project. In order to evaluate the results, many different
types of NFAs were converted to DFAs. More than ten NFAs, some with lambda transitions and
some without, were all converted to DFAs successfully. Additionally, the converted DFAs were
also verified with the procedure provided by JFLAP to convert NFAs to DFAs.
It has been already proved that if a language L is accepted by some NFA, then there will be some
equivalent DFA which also accepts L [1]. With this in mind, it can be reasonably concluded that
our algorithm is implemented correctly when the equivalent DFA created accepts and rejects the
same strings recognized by the original NFA. An example is provided to show how a string can be
checked to see if it would be accepted or rejected by either an NFA or DFA. If the string is
accepted or rejected by both the NFA and equivalent DFA, then our conclusion of the
implementation being correct becomes more confident. The algorithm is known to be correct
because it is based off the NFA and DFA equivalence proof.
Tests:
Figure 1:This is the NFA that we have taken to test our Program
Figure 3:NFA confirmation
Figure 2: This is the input data
Test
Because the NFA and its equivalent DFA in both
accept the string aba, it can be reasonably be
assumed that the two automatas accept the same
language. Please keep in mind that performing a
brute-force test of all possible strings in the
alphabet is time consuming. Because of this, it
difficult to truly prove whether two automatas are
equivalent by only testing and using examples.
Figure 4: Resulting DFA
Conclusion
Although the process of converting an NFA to a DFA seems simple when doing it manually, it is
much more complicated to convert this process into code. One of the most challenging parts
during development was to determine the transitions for the new state, It was necessary to look
at every state from the original NFA that compose the new state, then search for all the states in
the transition table and finally join the closure for those states. The use of data structures such
as classes and stacks facilitated the development.
There are a lot of details involved in creating the DFA. For example, the algorithm must keep
track of the initial and final states, check to see if a trap state is necessary, and perform the
closure of any lambda transitions present in the NFA, and so on. The algorithm needed to
handle all these details in order to create the correct DFA . Additionally, after the DFA is created,
there was also the reduction procedure which removed useless or repetitive states and
transitions.
References
[1]Linz, Peter. An Introduction to Formal Languages and Automata. Jones & Bartlett Learning,
. 2012.
[2] “Vis.js Community Edition *.” Visjs.org, https://visjs.org/
[3] “JFLAP.” JFLAP, http://www.jflap.org/
