c ++ 11 — реализация NFA в DFA в переполнении стека

Название говорит само за себя. Мне нужны некоторые идеи.
Вход nfa выглядит следующим образом и не имеет эпсилон-движений.

1 2
0 a 2
1 b 3

и т. д., что означает, что 1 и 2 являются конечными состояниями и что с помощью «а» я могу перейти из состояния 0 в состояние 2.

я использую

struct nod
{
int ns;
char c;
};

vector<nod> v[100];

сохранить данные, где v [i] — вектор, содержащий все пути, которые могут быть из состояния i.
Мне нужна идея о том, как назвать новые состояния, когда существует множество состояний, таких как

0 a 1
0 a 2
0 a 3

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

0

Решение

В худшем случае для NFA с n состояниями потребуется DFA с 2 ^ n состояниями: одно состояние для каждого подмножества состояний в NFA. Другой способ думать об этом состоит в том, что все состояния DFA могут быть помечены двоичной строкой длиной n, где k-й бит установлен в 1, если k-е состояние NFA включено в подмножество, которому соответствует состояние DFA.

Хорошо, это, возможно, плотное объяснение для разбора. Пример поможет. Предположим, что NFA имеет состояния 0, 1 и 2. Существует 2 ^ 3 подмножества состояний, поэтому у нашего DFA будет до 8 состояний. Строки битов следующие:

  • 000: пустой набор, не содержащий состояний
  • 001: набор, содержащий только состояние 0
  • 010: набор, содержащий только состояние 1
  • 100: набор, содержащий только состояние 2
  • 011: набор, содержащий состояния 0 и 1
  • 101: множество, содержащее состояния 0 и 2
  • 110: набор, содержащий состояния 1 и 2
  • 111: множество, содержащее все состояния

Мы можем интерпретировать эти строки битов как сами целые числа, и это дает нам естественный способ маркировать состояния DFA:

  • 0: пустой набор, не содержащий состояний
  • 1: набор, содержащий только состояние 0
  • 2: набор, содержащий только состояние 1
  • 3: набор, содержащий только состояние 2
  • 4: набор, содержащий состояния 0 и 1
  • 5: набор, содержащий состояния 0 и 2
  • 6: набор, содержащий состояния 1 и 2
  • 7: набор, содержащий все состояния

Единственная проблема с этим порядком состоит в том, что если вам не нужны все состояния (а часто нет), у вас могут быть (иногда большие) пробелы между используемыми состояниями. Ваш DFA может действительно нуждаться только в состояниях 1, 2 и 3 (например, если ваш NFA уже является минимальным DFA). Может быть, вам нужны только состояния 1 и 7. Другие возможности существуют.

Вы всегда можете отделить название и индекс для состояний, которые вы создаете, если вы создаете их по требованию. Если вы создали k состояний и создали новое состояние так, как вам это нужно, вы можете назначить ему индекс k + 1 и присвоить ему имя в соответствии с битовой строкой. Таким образом, ваши индексы плотно упакованы вместе, и вы можете проследить до подмножества состояний NFA через имя.

Мне нужна идея о том, как назвать новые состояния, когда существует множество состояний, таких как

Назовите их в соответствии с битовой строкой для соответствующего подмножества.

И как я могу проверить, был ли мультимножество уже преобразовано в состояние?

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

0

Другие решения

Других решений пока нет …