Алгоритм NFA к DFA

Question

Я прочитал текстовый файл символов, состояний и переходов и поместил все это в таблицу. Это выглядит так:
символы а, б
состояния q1, q2, q3, q4
начальное состояние q4
конечное состояние q2, q3

переходное состояние:
q4, эпсилон, q1
q1, a, q2
q3, a, q3
q3, b, q1

Я прочитал алгоритм преобразования NFA в DFA, но я не совсем понимаю этот алгоритм. Как бы я создал методы перехода и какой у меня должен быть класс состояний?

Answer 1

У меня есть отличная ссылка прямо здесь: JFLAP

JFLAP - это Java JAR, в который включена хорошая визуализация. Вы можете тестировать и преобразовывать NFA / DFA, делать Pummping Lemma Stuff и проверять различные грамматики и тому подобное ... Вы можете попробовать!

Answer 2

Эти две ссылки должны вам помочь:

http://www.win.tue.nl/prose/pres/ploeger-19-10-06.pdf
http://www.cs.sun.ac.za/rw711/documentation/hopcroft2.pdf

Answer 3

Есть ли у вас проблемы с программированием или проблема с автоматами?

Поскольку программирование это кажется очень простым. Да, у вас будет класс состояний с 4 возможными значениями q1-a4. Класс состояния имеет единственный конструктор, инициализирующий его как q4. Он имеет функцию Accept (symbol), которая модифицирует объект состояния, и, возможно, функцию IsEndState (), которая возвращает true для состояний q2 и q3.

Участие NFA / DFA вступает в игру при реализации метода Accept (). Теперь вам может потребоваться программное решение для преобразования реализации Accept () на основе NFA в реализацию Accept () на основе DFA.

Answer 4

Если вы хотите сделать это автоматически, не загружая что-то вроде JFLAP, дайте Онлайн-конвертеру NFA в DFA вращение.

Видео ProfBrown "Конвертировать NFA в DFA" на YouTube исследует, как это сделать в некоторой строгости, хотя ИМО нецелесообразно и излишне утомительно, когда приходится писать таблицы вручную. Когда вы привыкнете к этому процессу, вы сможете увидеть его на небольших графиках. В случае больших графиков вы все равно использовали бы инструмент для его автоматизации.