Моделирование DFA и NFA с помощью осуществления HashMap

Question

Я осуществить следующие операции над автоматами в Java:

• Concatenation
• Клини Звезда
• Союз
• Пересечения

Эти операции проще, если автомат является NFA. Мне понравилась реализация, приведенная в следующей ссылке Modelling a Finite Deterministic Automaton via this data, но я думаю, что это не очень хорошо подходит при моделировании NFA из-за ограничения единственности ключа. Не могли бы вы порекомендовать мне какое-либо решение для моделирования NFA?

Answer 1

Как кто-то, кто на самом деле реализованы эти операции один раз (при создании генератора сканера), я рекомендую создать автомат как NFA, а затем использовать алгоритм, подобный построению подмножества, или алгоритм Томпсона, чтобы преобразовать его в DFA. Это позволяет логично комбинировать автоматы вместе просто и элегантно, не жертвуя скоростью получаемого автомата соответствия.

Надеюсь, это поможет!

Answer 2

Я бы рекомендовал использовать DFA. Хотя формирование NFA может быть проще на бумаге, проверка правильной строки на NFA будет сложнее, чем проверка на DFA из-за учета эпсилон-прыжков.

Что касается моделирования их, вы должны иметь возможность писать свои собственные только с несколькими классами. Просто подумайте о том, что ДКА/НФ состоит из:
- начальное состояние
- множество состояний (некоторые из которых являются «принятие» состояния)
- Набор переходов