УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»



Главная

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

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

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

English
 Home

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


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

Яndex



   Главная / Курсовые проекты / Преобразование недетерминированного конечного автомата в детерминированный (версия для печати)


Преобразование недетерминированного конечного автомата в детерминированный



(С) 2003 г. А. А. Пестов, А. А. Шалыто

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Отсюда можно скачать полный текст документации в формате pdf (287 кб)
Отсюда можно скачать приложение (23 кб)
Исходные тексты (45 кб)

Аннотация

SWITCH-технология весьма удобна для программной реализации систем управления техническими объектами. Эта технология использует понятие “детерминированный конечный автомат”.

Однако существуют задачи, для которых исходную формализацию целесообразно выполнять с помощью недетерминированных конечных автоматов.

Кратко поясним, что такое детерминированный конечный автомат, и чем он отличается от недетерминированного конечного автомата.

Детерминированный конечный автомат - это автомат, в котором каждый переход строго регламентирован. В таком автомате при поступлении входного воздействия однозначно определяется следующее состояние.

В недетерминированном конечном автомате допускаются состояния, в которых по одному входному воздействию могут произойти переходы в различные состояния. При появлении входного воздействия этот автомат “размножается” - создаются копии автомата, в каждой из которых выполняется соответствующий переход из рассматриваемого состояния. Считается, что недетерминированный конечный автомат достигает конечного состояния, если хотя бы одна из его “копий” перейдет в свое конечное состояние. При проектировании конкретных программ, в отличие от теории, применять такие автоматы невозможно, так как на практике нельзя “хаотично” создавать копии.

Недетерминированные конечные автоматы бывает полезно использовать на ранних стадиях проектирования, когда еще не требуется добиваться “полной” четкости в описании поведения системы, так как это упрощает формализацию. При этом переход от недетерминированного конечного автомата к детерминированному конечному автомату осуществляется на последующих стадиях. Недетерминированные конечные автоматы могут применяться при обработке текстов, например, при поиске подстрок. Именно эта задача и рассматривается в данной работе в качестве примера.

Она посвящена разработке программы преобразования недетерминированного конечного автомата в детерминированный конечный автомат на основе алгоритма К. Томпсона. Кроме того, эта программа позволяет устранять вершины, недостижимые из начальной.

Программа написана на языке программирования С++ с использованием библиотеки классов MFC.


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