SAINT-PETERSBURG STATE UNIVERSITY OF INFORMATION TECHNOLOGIES, MECHANICS AND OPTICS
“Programming Technologies” Department

Transformation none determinate finite automaton into determinate finite automaton

(С) 2003 A. A. Pestov, A. A. Shalyto

Saint-Petersburg State University of Information Technologies, Mechanics and Optics

From here it is possible to download the full text of documentation in Russian in a PDF-format (287 Kb)
Here is application (23 Kb)
Source code (45 Kb)

Annotation

SWITCH-technology is very convenient. for the system of technical objects management. This technology use idea of determinate finite automaton (DFA).

But there are exist tasks, where the initial formalization advisability construct with using the idea of none-determinate finite automaton (NFA).

Will give explanation of the difference between DFA and NFA.

DFA – it is the finite automaton, with property, that every his crossing definite in one way. In that kind of automatons on input action uniquely determinate his next state.

NFA it is possible to have the states, which on the one input action may happen crossing to the different states. On that’s input actions NFA is duplicated, creates automaton copies, each of them make corresponding crossing. Consider NFA reach the final state that case if someone of his “copies” reach in her final state. On the designing concrete programs, NFA is not usefull, because on the practic impossible to create copies in random order.

But sometimes NFA useful to use on the early-stages projecting, when request of full accuracy is not keenly stand. This allow to simplify formalization. And the conversion from NFA to DFA realize on the next stages. NFA may to be using on the text parsing, for example, on substring searching. Exactly this task will be looked in that text as example.

Current task dedicate building program of transformation NFA to DFA. It based on the algorithm of K. Thompson. Besides this program allow to delete vertex, which are not reached from the start state.

Program was written on the programming language C++ with usign features libraries and classes MFC.