Как написать программу, которая будет читать множество состояний FSM. Входные данные будут из текстового файла с форматом (состояние ввода следующего состояния), а последняя строка - конечным. например:Как создать машину конечного состояния в Java
s0 a s1
s1 a s2
s2 a s2
s1
Выход программы будет:
а) перечень строки, порожденной FSM.
б) Программа может определить, является ли FSM является DFA или NDFA и распечатать результат
Я не собираюсь давать вам кодированное решение, но некоторые направления мысли.
Прежде всего, FSMs должны иметь начальные состояния и конечные состояния, поэтому вам не хватает важной информации.
Если вы создаете список строк, вы, вероятно, имеете дело с очень ограниченным подмножеством FSM, которые принимают конечное число строк. Поэтому разумно попробовать любую возможность; следовать по каждому пути через график и печатать каждый раз, когда вы нажимаете конечное состояние.
Подумайте о том, что отличает DFSM от NDFSM. Он не является детерминированным, если есть несколько способов пойти с некоторым вводом. Итак, когда вы строите свой график, если у вас когда-либо есть узел с двумя идентичными переходами в разные состояния, это не детерминировано. Поскольку любой недетерминизм делает всю систему недетерминированной, детерминизм - это просто полное отсутствие недетерминированности.
Итак, вы, вероятно, захотите начать с создания представления. Приходят на ум два простых способа. Более визуально вы можете создать график. Самый простой способ сделать это - создать класс узла, затем объект для каждого узла, содержащий пары переходов и пунктов назначения.
Способ, которым я предпочитаю представлять FSMs, имеет хеш-карту/словарь. Используйте узел и переход как ключ с назначением в качестве значения. Это делает навигацию довольно простой.
Удачи вам!
EDIT: При определении индетерминизма, не забывайте думать о эпсилоне переходах (как я только что сделал на секунду :).)
СПАСИБО за ваши указания. У меня есть программа, которая может просматривать входной файл, а затем извлекать данные и сохранять все состояния и входы в массивы. Но после этого я понятия не имею, с чего начать и не могу понять, каким будет алгоритм. Как вы знаете, строка может быть разной, пока путь достигнет конечного состояния. Это означает, что строка может быть более одной. Как заставить программу ее вычислить? Я не прошу полного кодирования, по крайней мере, пожалуйста, дайте несколько снимков алгоритма, который поможет мне понять это. –
Это, вероятно, будет проще всего с рекурсией. Итак, напишите способ перемещения по графику. Запустите метод в любом состоянии. Затем найдите все возможные переходы оттуда. Рекурсивно вызывается метод, в котором вы находитесь, каждый раз переходя к новому состоянию. Вы можете увидеть, как это разветвляется с множеством рекурсивных вызовов, чтобы принимать все возможные пути через FSM (иначе, принимая все возможные строки, которые он принимает). Итак, теперь ваш базовый пример: это когда вы достигнете конечного состояния. Затем вы можете просто распечатать путь, который требуется, чтобы добраться туда. – akroy
Когда вы проходите через график, если у вас когда-либо есть два идентичных перехода (или переход эпсилон к идентичному переходу), вы определили, что он не детерминирован. – akroy
ли это домашнее задание? Что вы пробовали? –
@home нехорошо просить полного решения, он должен продемонстрировать значительные усилия. –