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