Как я представляю переходы при написании кода для динамического DFA? - PullRequest
Новая
       66

Как я представляю переходы при написании кода для динамического DFA?

0 голосов
/ 30 апреля 2018

Я хочу написать Java-программу для создания динамических конечных автоматов для любого языка с любым алфавитом, а затем протестировать машину на прием или отклонение любого заданного слова.

Я ввел номер состояния, алфавит, начальное состояние и конечное состояние (я), но остановился на записи переходов, которыми в основном являются конечные автоматы.

1 Ответ

0 голосов
/ 30 апреля 2018

Это хороший проект. Как вы говорите, вы должны сначала тщательно определить язык ввода для описания любой FA. В дополнение к тому, что у вас уже есть, вам понадобятся переходы между состояниями. Обычно это делается одним из двух способов:

  1. Полная таблица переходов.
  2. Описание графа переходов, в котором отсутствующие ребра интерпретируются как переход к «падению». Т.е. переход в состояние «черная дыра», неприемлемое состояние с самоконтролем для всех символов языка.

Форма 1 проще для чтения, но гораздо менее удобна, потому что вы должны явно указать все переходы. Форма 2 удобнее. Я рекомендую форму 2. Описание DFA с этой формой может выглядеть следующим образом: 

4  # There are 4 explicit states (plus a 5th for the "black hole")
   # Assume they have state numbers 0 (the start state), 1, 2, 3.
ab # A string of characters in the FSM alphabet
1 3 # Numbers of accepting states.
5 # Number of explicit state transitions
0 1 a # From 0 to 1 on input a
1 1 a # From 1 to 1 on input a
1 2 b # From 1 to 2 on input b
2 3 a # From 2 to 3 on input a
3 3 a # From 3 to 3 on input a

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

Обратите внимание, что полностью указанный DFA с 4 состояниями и 2 входными символами имеет 2 (4) (4-1) = 24 перехода, и мы дали только 5 из них на этой машине. Чтобы заполнить оставшиеся, добавьте состояние «черная дыра» 4. Это имеет самоконтроль для всех символов. Для каждого узла i, где отсутствует исходящий переход для некоторого символа c, добавьте переход i 4 c для завершения DFA.

Для представления DFA в Java хорошим выбором будет Map<Integer, Map<Character, Integer>>. Первый ключ карты - это номер штата. Вторым является входной символ. Конечным значением является другой номер состояния. Так что если вы в данный момент находитесь в состоянии s и входной символ c, вы получите следующее состояние с чем-то вроде 

nextState = transitionMap.get(s).get(c)

Обратите внимание, что нет необходимости явно добавлять состояние 4 или все переходы к нему. Скорее, при оценке вышеприведенного выражения просто заставьте машину отказаться в любое время, когда nextState окажется null.

...