Abstract:

The term “automata” originates from the greek word “αυτόματα” and refers to “self-acting” machines which are designed to automatically follow predetermined sequences of operations. Automata theory studies how computations are performed by machines and makes a focal part of any core curriculum in computer science and engineering. In its context, automata are mathematical models for abstract machines which describe what can be done with computers of varying amounts of memory. Finite Automata describe what can be done with computers of very limited (i.e., finite) amount of memory, corresponding to their limited number of states, in a similar way that Turing machines abstract what can be done with ordinary computers. Finite Automata describe algorithms by explaining all the different states such procedures can be in, the events that can occur in each state, what actions are taken in response to the events and what transitions happen as a result. Procedures usually start in a particular beginning state and, then, follow a sequence of steps to get it into a regular operating state, and move to other states in response to particular types of input or other circumstances. There are Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA). A DFA can only go to one state from another, whereas an NFA may have the option to explore multiple states. However, this fact reflects only design simplicity since DFA and NFA are equivalent in terms of computational power. In fact, for every NFA an equivalent DFA can be constructed via a standard conversion process known as “powerset construction” or “subset construction” which eliminates the NFA ambiguity.

In this work, we present N2D, an online application which computes an equivalent DFA for any given NFA. More precisely, users create the initial NFA by adding states and transitions among them via a simple and easy-to-use graphical environment. Then, N2D, using the user-created NFA as input, computes and returns as visualized output an equivalent DFA via the provably correct “powerset construction” procedure. Both the initial NFA and the equivalent DFA computed are visualized and can be downloaded as image files. N2D is a lightweight and user-friendly application developed using Javascript, HTML, CSS and the Graphviz open source graph visualization software.

N2D can certainly be of practical usefulness both in academic and applied contexts. N2D can be exploited for student education and training both in real or virtual learning environments. In the context of courses on Theory of Computation or Computational Complexity, students are expected to understand and exploit the NFA-DFA equivalence. N2D can certainly assist students in their study and help them enhance their understanding, knowledge, and skills. Furthermore, N2D can be exploited in industry since finite automata have several real-world applications including pattern matching, analysis of message-passing protocols, lexical analysis, proprocessing natural language, etc, while several mechanical devices, like elevators, vending machines, and traffic-sensitive traffic lights, are usually designed and implemented using DFAs. The concepts embodied by DFAs can be translated into hardware or software. It is more difficult to translate an NFA into an implementation because of its complexity, though it is always possible to design an equivalent DFA and N2D is an application to serve also this purpose.

Keywords:

Finite automata, NFA-DFA equivalence, online application, graphical environment, Javascript, HTML, CSS, Graphviz, education, training, real-world applications.