В DFA мы можем выполнить пересечение двух автоматов, выполняя кросс-произведение состояний двух автоматов и принимая те состояния, которые принимают в обоих начальных автоматах. Союз выполнен аналогичным образом. Как бы то ни было, хотя я могу сделать объединение в NFA легко используя переход epsilon, как я могу сделать их пересечение?Как найти пересечение двух NFA
Вы можете использовать кросс-товарную конструкцию на NFA так же, как и DFA. Единственные изменения в том, как вы будете обрабатывать & epsilon; -переходы. В частности, для каждого состояния (д я, г J) в автомате кросс-продукта, вы добавьте & эпсилон; -переход из этого состояния каждой пары состояний (д к, г J), где есть более & эпсилон; -переход в первой машине от ц я к д к и каждой паре состояний (д я, г к), где есть более & эпсилон; -переход во второй машине от г j до r k.
Кроме того, вы всегда можете преобразовать NFA в DFA, а затем вычислить перекрестное произведение этих DFA.
Надеюсь, это поможет!
Альтернатива построению автомата продукта допускает более сложные критерии приемлемости. Обычно NFA принимает входную строку, когда она достигла любого из набора принимающих конечных состояний. Это можно расширить до булевых комбинаций состояний. В частности, вы строите автомат для пересечения, как и для объединения, но считайте, что полученный автомат принимает входную строку только тогда, когда она находится в (что соответствует), принимая конечные состояния в обоих автоматах.
Мы также можем использовать De Morgan's Laws: а пересечение B = (A»U B„)“
Принимая объединение комплиментов два НКИ сравнительно проще, особенно если вы привыкли к методу эпсилона союз.
Хм ... как вы принимаете отрицание NFA, кроме как сначала превращая его в DFA? – Stefan
Существует огромная ошибка в ответе templatetypedef.
продукт автомат L1 и L2, которые являются NFAS:
новых состояний Q = произведение состояний L1 и L2.
теперь функция переход:
а является символом в объединении обоих автоматов алфавитов
дельты ((q_1, Q_2), а) = delta_L1 (q_1, а) X delta_L2 (q_2, a)
, что означает, что вы должны умножить набор, являющийся результатом delta_L1 (q_1, a), с помощью набора, который получается из delta_L2 (q_1, a).
Проблема в ответе templatetypedef заключается в том, что результат продукта (qk, rk) не упоминается.
Probabaly поздний ответ, но поскольку у меня была проблема с similair, сегодня я чувствовал себя делить ее. Сначала осознайте смысл пересечения.Здесь это означает, что данная строка e, e должна приниматься обоими автоматами.
Рассмотрим на следующие автоматы:
Intiuitivly м = м1 ∩ м2 это автомат принимает строки, содержащие как «11» и «00» в качестве подстроки. Идея состоит в том, чтобы одновременно имитировать оба автомата.
Теперь давайте официально определим пересечение.
м = (Q, Σ, Δ, q0, F)
Давайте начнем с определения состояния для м это, как уже упоминалось выше carthesian продукта состояний в m1 и m2. Таким образом, если мы имеем a1, a2 как этикетки для государств в m1 и b1, b2 состояния, в м2, Q будет состоять из следующих состояний: A1B1, a2b1, a1b2, a2b2. Смысл этого заключается в том, чтобы отслеживать, где находятся как m1, так и m2.
Σ, скорее всего, остается тем же, однако в некоторых случаях они отличаются, и мы просто возьмем объединение алфавитов в m1 и м2.
д0 теперь состояние, в Q, содержащий как начальное состояние m1 и начальное состояние м2. (A1B1, чтобы дать пример.)
Р содержит государственную с если и только если оба государства упоминается в с являются принимают состояния m1, м2 соответственно.
Последнее, но не менее А; мы определяем дельта снова в терминах carthesian продукта, следующим образом: Д (A1B1, E) = Δ (м1) (a1, Е) х Д (м2) (б1, Е) как и в одном из ответов выше, если я не ошибаюсь. Интуитивная идея заключается в том, чтобы просто разделить a1b1 и рассмотреть состояния a1 и b1 в их оригинальном автомате. Теперь мы «итерации» каждого возможного края, например, выбираем E, и видим, где он приводит нас в исходные автоматы. После этого склеиваем эти результаты вместе с помощью картофельного продукта. Если (a1, E) присутствует в m1, но не Δ (b1, E) в м2 край не будет существовать в м, в противном случае мы будем иметь какой-то союзного строительства ,
так что нет простого метода, как просто добавить epsilon, как в случае соединения? –
@ AdityaNambiar - Не знаю, насколько я знаю. – templatetypedef
Другой ответ здесь вызвал озабоченность отсутствием «одновременных ε-переходов», где обе машины одновременно выполняют ε-переход. Я еще не нашел никаких проблем с их упущением, так как эти переходы могут выполняться в несколько шагов в любом случае, но, возможно, есть какой-то странный случай с краем. Не могли бы вы прояснить это? – harold