#intersection #finite-automata #dfa #nfa
#пересечение #конечные автоматы #dfa #nfa
Вопрос:
Если два DFA, для которых должно быть вычислено пересечение, не указаны полностью, может случиться так, что возможно достичь состояния, содержащего только одно состояние из двух DFA. Это правильно или требуются дополнительные шаги, прежде чем перейти к вычислению пересечения?
Комментарии:
1. Не могли бы вы подробнее рассказать о том, что вы подразумеваете под «не полностью определенным»? Как вам даны автоматы?
2. Некоторые состояния не имеют переходов для всех входных символов. Итак, если «Q0» указано не полностью, это означает, что, учитывая 0 и 1 в качестве входных символов, «Q0» имеет только переход для 0 из «Q0» в другое состояние.
Ответ №1:
Учитывая DFA, в котором отсутствует переход в некотором состоянии, вы всегда можете преобразовать его в «полный» DFA, добавив в новое состояние qмертвый, который не принимает и имеет переходы только к себе, затем добавляя переходы в qмертвый для каждого пропущенного перехода. Таким образом, в этом смысле, если у вас не указаны полные DFA, вы всегда можете преобразовать DFA в «полные» DFA, а затем запустить построение кросс-продукта как обычно.
Однако, если вы специально создаете DFA для пересечения двух входных DFA, вам не нужно этого делать, потому что все состояния, сгенерированные таким образом, будут эквивалентны друг другу (ни одно из них не может достичь принимающего состояния на исходной машине). Существует несколько способов формирования пересечений, и в зависимости от того, какой подход вы выберете, вы можете внести любые изменения от незначительных до крупных:
- Один алгоритм просто вычисляет все возможные пары состояний из двух входных DFA, а затем заполняет переходы, просматривая, куда переходят пары состояний. Если вы используете этот подход, вы можете просто сделать так, чтобы каждое состояние, в котором отсутствует переход в одном из входных DFA, не имело переходов в перекрестном произведении, имитируя «один из автоматов умер бы здесь».
- Другой алгоритм использует DFS или BFS только для построения достижимых состояний в перекрестном произведении. В этом случае никаких изменений не требуется — если вы найдете пару состояний, в одном из которых отсутствует переход, просто не добавляйте никаких последующих состояний.
С другой стороны, если вы делаете что-то вроде конструкции объединения, где вам нужно только одно из двух состояний для принятия, эти подходы не будут работать, потому что вам нужно иметь возможность имитировать идею «один автомат умер, а другой все еще успешно работает». Для этого добавление в явном мертвом состоянии является простым и эффективным подходом.