Внедрение недетерминированного конечного автомата (NFA)

Question

Я пытаюсь разработать симуляцию, которая выполняет не детерминированный конечный автомат в Java. Первый аргумент командной строки - это текстовый файл, который определяет машину. Второй аргумент - входная строка. Если он принимает строку, он печатает на стандартный вывод «accept», за которым следует список состояний accept, в котором он может закончиться. Если он отклоняет, он выдает «reject», а затем список всех возможных конечных состояний.

Например, текст:

state 1 start 
state 2 
state 7 accept 
transition 1 0 1 
transition 1 1 1 
transition 1 0 2 
transition 2 0 2 
transition 2 0 1 
transition 2 1 1 
transition 2 0 7 
transition 7 0 7 
transition 7 1 7 

, который выглядит следующим образом:

с входной строкой 10 будет выходные

reject 1 2 

и с входной строкой из 000 будет производить

accept 7 

Мне нужен совет относительно того, какие структуры данных использовать. Я думал об использовании hashmaps и наборов, но я не уверен.

Answer 1

Я думаю, вы должны transform ваш автомат в детерминированный, а затем сделать очевидным.

Есть три распространенных способа реализации конечного автомата в программном обеспечении:

• Составляют переходную функцию в виде таблицы (2D массива) и после каждого символа чтения, просмотра следующего состояния в нем.
• Используйте вложенные операторы switch для текущего состояния и символа ввода, чтобы явно определить следующее состояние в коде.
• Использование шаблона состояния : представление каждого состояния как класса с методом, возвращающим следующее состояние, с учетом входного символа.

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

Для Downvoters: Вы не написать детерминированную программу, которая «исполняет» недетерминированное автомат. Однако, по довольно фундаментальной теореме теоретической информатики, вы можете превратить 0 недетерминированный конечный автомат в детерминированный полностью автоматизированный процесс, то есть детерминированный алгоритм, который может быть легко реализован в программном обеспечении. Каждый студент-информатика должен был выполнить эту процедуру хотя бы один раз, используя карандаш и бумагу. Если вы это сделаете, вы быстро увидите, как отслеживать состояние состояний исходного автомата, в которые входят состояния детерминированного. Затем просто имитируйте последний, посмотрите, в каком состоянии он заканчивается, и выведите состояния исходного недетерминированного автомата, которые его составляют.

Answer 2

NFA означает, что вы можете иметь набор состояний за раз. Таким образом, чтобы представить текущее состояние NFA, используйте Set interface.

Установить интерфейс гарантирует, что не будет никаких дубликатов состояния. Это важно, поскольку NFA имеет более одного состояния за раз. Если вы используете какой-либо другой набор данных, этого gurrentee нет. В случае NFA вероятность наличия повторяющегося состояния в каждом переходе экспоненциальна. Но множество состояний всегда конечное. Set interface гарантирует, что ваш текущий набор будет заполнен дубликатами.

Для использования в пространстве и производительности вы можете использовать Enumset в качестве Enumset, используя бит-векторы для хранения состояния внутри.

Алгоритм:

Initialise, чтобы начальное состояние

Process строку справа налево, начиная с индекса 0;

для символа при обновлении с использованием перехода состояния;

Если какой-либо из этих переходов приводит к окончательному состоянию, что означает, что строка принимается.