Перекрестное произведение неполных DFA

Question

Я пытаюсь сделать кросс-продукт между двумя DFA, но они оба являются неполными DFA.

Следующее изображение - это ответ, который я придумал для пересечения перекрестного произведения между двумя неполными DFA. Алфавит {a, b, c, d, e}.

Является ли это правильно или делает тот факт, что они являются неполными изменить все?

Answer 1

Тот факт, что они неполные, делает вашу работу отличной, если вы строите кросс-продукт, чтобы найти объединение; однако для пересечения вы все равно можете использовать этот базовый подход. Но, вы сделали некоторые ошибки:

Давайте начнем в верхнем левом углу, и смотреть на все переходы из состояния A1:

Во-первых, у вас есть переходное состояние маркированы c из состояния A1 заявить A2. Однако это неверно, потому что нет перехода от A в A в верхнем DFA, помеченном c. Затем у вас есть переход с отметкой a, который переходит из состояния A1 в себя. Это также неверно, потому что переход от состояния 1 к чему-либо помечен как a. Аналогично, нет перехода из состояния 1 с пометкой b, что также приведет к аннулированию вашего перехода от A1 до B1.

При работе с неполной ДКОЙ и делает кросс-продукт, как это, вы будете иметь только исходящие ребра для государства (p,q), когда есть письмо, что и состояние p и состояние q имеют исходящие ребра для.

Следовательно, переходы из состояния начала отсутствуют. На этом этапе мы можем перестать работать, потому что без переходов из состояния начала нет смысла - итоговый DFA ничего не соответствует.

Другая возможность того, как подойти к этому, состоит в том, чтобы сначала сделать оба DFAs завершенными, добавив не принимающее состояние (я вызываю это состояние ∅). Это состояние должно иметь к нему преимущество от каждого состояния для каждой буквы, для которой уже нет другого исходящего края. Например, в первом DFA будет край от A до ∅ для c, d и e. Кроме того, для каждой буквы должен быть край от ∅ до ∅. Теперь оба DFA завершены.

Когда вы сделаете это, вы в конечном итоге с ребрами из A1 собирается: A∅ для a, B∅ для b, ∅1 для c и ∅∅ для d и e. Остальное остается как упражнение, но если вы его полностью вычеркнете, вы снова обнаружите, что нет пути от A1 до любого принимающего состояния.

Создание и ДКА завершения первого, на самом деле то, что вам нужно сделать, если вы построения кросс-продукта, чтобы найти союз - с пересечением это допустимо, чтобы просто выбросить любое состояние с участием ∅ в любом DFA после достижения ∅ означает, что вы никогда не достигнете принимающего состояния, но с союзом вам нужно сохранить их, потому что некоторые состояния, связанные с ∅, могут принимать состояния кросс-продукта. (Вы все еще можете выбросить состояние ∅∅ и любое к нему)