NFA для реализации DFA в C++

Question

Название говорит само за себя. Мне нужны некоторые идеи. Вход 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 или что-то подобное.И как я могу проверить, был ли мультимножество уже преобразовано в состояние?

Answer 1

В худшем случае для 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 через имя.

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

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

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

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