ITMO University
“Programming Technologies” Department



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Биоинформатика
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



    / Projects / Transformation none determinate finite automaton into determinate finite automaton (версия для печати)


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.


© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com