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

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

Я получил все остальное под контролем, генератор автоматов, стек ... Я делаю это в 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 и попытаться запустить каждый объект, но он не работает.

источник

2009-04-27 shake

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

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

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

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

источник

2009-04-28 00:19:42

Не было вопроса о * push-down * automata? – avakar

Несомненно. И каково определение пускового автомата? Стек с конечным контроллером состояния. Таким образом, вы делаете недетерминированный КПК как стек с недетерминированным контроллером конечного состояния. Решите проблему моделирования NFA, и у вас есть NPDA и NTM. –

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

источник

2010-06-11 19:37:58

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

ответ

Смежные вопросы