Симулятор для недетерминированного автомата Push-Down

Question

Ну, мне нужно сделать симулятор для недетерминированного автомата Push-Down. Все хорошо, я знаю, что мне нужно сделать рекурсию или что-то подобное. Но я не знаю, как сделать ту функцию, которая бы имитировала автомат.

Все остальное под контролем, генератор автоматов, стек ... Я делаю это в Java, так что, возможно, это единственная проблема, с которой может столкнуться человек, и я сделал это Так что, если кто-то сделал что-то подобное, я мог бы использовать советы.

Это моя текущая организация кода:

Classes:  class transit:
  list<transit> -contains non deterministic transitions
  state
  input  sign
  stack sign class generator
  it generate automaton from file clas NPA
  public boolean start() - this function I am having trouble with

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

Я попытался решить эту проблему с помощью набора объектов NPA и попытаться запустить каждый объект, но он не работает.

Answer 1

Хорошо, подумайте об определении автомата. У вас есть состояния и функция перехода между состояниями. У вас есть стек. Что делает жизнь захватывающей, так это недетерминизм.

однако, это теорема (посмотрите), что каждый недетерминированный конечный автомат имеет эквивалентный детерминированный FSA.

Один из подходов, которые вы можете попробовать, - это создать эквивалент DFA. Однако в худшем случае это экспоненциальное пространство: каждое состояние в DFA сопоставляется с подмножеством набора состояний состояний NFA.

Так что вы можете попробовать это "на линии". Теперь вместо создания эквивалентного DFA вы моделируете NFA; при переходах между состояниями вы создаете все последующие состояния, которые достигли, и помещаете их в некоторую структуру данных; затем вернитесь и посмотрите, что будет дальше для каждого такого состояния.

Answer 2

JFLAP с открытым исходным кодом и делает это (и многое другое!) - почему бы не проверить это?