Как создать конечный автомат на Java

Как написать программу, которая будет читать набор состояний конечного автомата. Входные данные будут из текстового файла с форматом (состояние ввода следующего состояния), а последняя строка будет конечным состоянием. Например :

    s0   a   s1
    s1   a   s2 
    s2   a   s2 
    s1

Вывод программы будет:

а) Список строк, сгенерированных автоматом.

б) Программа может определить, является ли конечный автомат DFA или NDFA, и распечатать результат.


java state-machine fsm
person akmal elias    schedule 16.06.2012    source источник
comment
Это домашнее задание? Что ты пробовал?   -  person Tomasz Nurkiewicz    schedule 16.06.2012
comment
@home не следует просить комплексное решение, он должен продемонстрировать значительные усилия.   -  person Seçkin Savaşçı    schedule 16.06.2012

Ответы (1)


arrow_upward
2
arrow_downward

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

Прежде всего, конечным автоматам нужны начальные и конечные состояния, поэтому вам не хватает важной информации.

Если вы создаете список строк, вы, вероятно, имеете дело с очень ограниченным подмножеством автоматов, которые принимают конечное количество строк. Поэтому разумно попробовать все возможности; проследите каждый путь по графику и печатайте всякий раз, когда вы попадете в конечное состояние.

Подумайте, что отличает DFSM от NDFSM. Это недетерминировано, если есть несколько способов ввода некоторого ввода. Итак, когда вы строите свой график, если у вас когда-либо есть узел с двумя идентичными переходами в разные состояния, это недетерминировано. Поскольку любой недетерминизм делает всю систему недетерминированной, детерминизм - это просто полное отсутствие недетерминизма.

Итак, вы, вероятно, захотите начать с создания представления. На ум приходят два простых способа. Более наглядно можно построить график. Самый простой способ сделать это - создать класс узла, а затем объект для каждого узла, содержащий пары переходов и мест назначения.

Я предпочитаю представлять конечные автоматы с помощью хеш-карты / словаря. Используйте узел и переход в качестве ключа с местом назначения в качестве значения. Это делает навигацию довольно простой.

Удачи!

РЕДАКТИРОВАТЬ: при определении недетерминизма не забудьте подумать о переходах эпсилон (как я только что сделал в течение секунды. :))

person Cannoliopsida    schedule 16.06.2012
comment
СПАСИБО за ваши направления. Я заставил программу просматривать входной файл, затем извлекать данные и сохранять все состояния и входные данные в массивах. Но после этого я понятия не имею, с чего начать, и не могу понять, каким будет алгоритм. Как вы знаете, строка может быть другой, пока путь достигает конечного состояния. Это означает, что строка может быть больше одной. Как сделать так, чтобы программа могла это вычислить? Я не прошу полного кодирования, по крайней мере, пожалуйста, дайте несколько изображений алгоритма, которые могут помочь мне понять его. - person akmal elias; 16.06.2012
comment
С рекурсией, наверное, будет проще всего. Итак, напишите метод путешествия по графу. Запустите метод в любом стартовом состоянии. Затем пусть он найдет все возможные переходы оттуда. Рекурсивно вызывайте метод, в котором вы находитесь, переводя каждый возможный переход в новое состояние. Вы можете увидеть, как это разветвляется с множеством рекурсивных вызовов, чтобы пройти все возможные пути через конечный автомат (иначе говоря, принимая каждую возможную строку, которую он принимает). Итак, теперь ваш базовый случай: это когда вы достигнете конечного состояния. Затем вы можете просто распечатать путь, по которому вы туда попали. - person Cannoliopsida; 16.06.2012
comment
По мере того, как вы просматриваете график, если у вас когда-либо было два идентичных перехода (или эпсилон-переход к одинаковому переходу), вы определили, что он недетерминирован. - person Cannoliopsida; 16.06.2012