Я прочитал текстовый файл символов, состояний и переходов и поместил все это в таблицу. Выглядит это следующим образом:
символы a, b
состояния q1, q2, q3, q4
начальное состояние q4
конечное состояние q2, q3
переходное состояние:
q4, эпсилон, q1
q1, a, q2
q3, a, q3
q3, b, q1
Я прочитал алгоритм преобразования NFA в DFA, но я не очень понимаю алгоритм. Как мне создать методы перехода и какой у меня должен быть класс состояния?
у меня есть отличная ссылка прямо здесь: JFLAP
JFLAP — это Java JAR, в который включена хорошая визуализация. Вы можете тестировать и преобразовывать NFA/DFA, делать прокачку Lemma Stuff и проверять различные грамматики и тому подобное... Вы можете попробовать!
У вас есть проблема с программированием или проблема с автоматами?
Потому что программирование это кажется очень простым. Да, у вас будет класс состояния с 4 возможными значениями q1-a4. Класс состояния имеет единственный конструктор, инициализирующий его значением q4. У него есть функция Accept(symbol), которая изменяет объект состояния, и, возможно, функция IsEndState(), которая возвращает true для состояний q2 и q3.
Часть NFA/DFA вступает в игру при реализации метода Accept(). Теперь может случиться так, что вас попросят найти программное решение для преобразования реализации Accept() на основе NFA в реализацию Accept() на основе DFA.
Эти две ссылки должны вам помочь:
http://www.win.tue.nl/prose/pres/ploeger-19-10-06.pdf
http://www.cs.sun.ac.za/rw711/documentation/hopcroft2.pdf
Если вы хотите сделать это автоматически, не загружая что-то вроде JFLAP, отправьте онлайн-NFA в DFA. инструмент преобразования спина.
В видео ProfBrown "Конвертировать NFA в DFA" на YouTube показывает, как это сделать в некоторых строгость, хотя ИМО непрактично и излишне утомительно писать таблицы вручную. По мере того, как вы привыкнете к этому процессу, вы сможете на глаз находить небольшие графики. В случае больших графиков вы все равно использовали бы инструмент для его автоматизации.
