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

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

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

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

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

Аннотация

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

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

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

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

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

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

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

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