Объединение детерминированных конечных автоматов

Вы можете использовать следующие простые шаги для создания комбинированного DFA.

Пусть Σ = {a₁ , a₂ , ...,a_k .
1-й шаг: спроектируйте DFA для обоих языков и назовите их состояние Q₀, Q₁, ...

2-й шаг: переименуйте каждое состояние в обоих DFA уникальным образом, т. е. переименуйте все состояния в DFA как Q₀, Q₁, Q_{2< /sub>, Q3 , ... при условии, что вы начали с нижнего индекса 0; это означает, что ни один из штатов не будет иметь такое же название.}

3-й шаг. Создайте таблицу переходов (δ), выполнив следующие действия.

3a. Начальное состояние комбинированного DFA:
      Возьмите начальное состояние обоих DFA (DFA1 и DFA2) и назовите их как Q_{[ i , j ]} где i и j — нижний индекс начального состояния DFA1 и DFA2 соответственно; т. е. Q_i — это начальное состояние 1-го DFA, а Q_j — начальное состояние 2-го DFA и пометить Q_{[i , j]} как начальное состояние. комбинированного ДФА.

3b. Сопоставить состояние обоих DFA как
           если δ(Q_i,a_k) = Q_{p1 и δ(Qj,ak) = Qp2 , где Qp1 принадлежит DFA1 и Qp2 принадлежит DFA2, тогда  δ(Q[ i , j ] , ak) = Q[p1,p2]< /под>}

3с. заполнить всю таблицу, пока в таблице переходов остается Q_[i,j].

3D. Окончательное состояние комбинированного DFA:
      Для случая AND окончательным состоянием будут все Q_{[i , j]}, где Q_i и Q_j > являются окончательным состоянием DFA1 и DFA2 соответственно.
      Для случая OR окончательным состоянием будут все Q_{[i , j]}, где либо Q_i, либо Q_j — конечное состояние DFA1 и DFA2.

4-й шаг: переименуйте все Q_{[i, j]} (уникально) и нарисуйте DFA, это будет ваш результат.

Пример:

L= {w: w has at least two a's and an odd number of b's}.

Шаг 1.
DFA для нечетного числа букв b .

DFA не менее чем для 2 а.

Шаг 2.
Переименуйте область DFA1

Шаг 3(a,b,c):
Построенная таблица переходов будет такой.

Шаг 3d:
Поскольку мы должны взять И для обоих DFA, поэтому конечное состояние будет Q_[2,4] , так как оно содержит конечное состояние оба DFA .
Если нам нужно использовать ИЛИ обоих DFA, конечное состояние будет Q_[0,4],Q_{[2,3 ]},Q_[1,4],Q_[2,4] .
Таблица переходов хотела бы это после добавления окончательного состояние .

Шаг 4.
Переименуйте все состояния Q_[i,j]
Q_[0,3] в Q _>0
от Q_[1,3] до Q₂
Q_[0,4] до Q₁
Q_[2,3] до Q₄
Q_[1,4] в Q₃
Q_[2,4] в Q₅
Таким образом, окончательный DFA будет выглядеть так, как показано ниже.

Язык L, где a равно как минимум двум, а b нечетным, является обычным языком. Его DFA выглядит следующим образом:

В этом DFA я концептуально объединил два DFS!

DFA-1 = for odd number of `b`'s (placed vertically three times in diagram)
DFA-2 = for >=  two a           (placed Horizontally two times in diagram)

_{DFA слишком симптоматичен и прост, поэтому я не думаю, что нужно говорить о том, как объединить оба DFA}

Чтобы нарисовать этот DFA, вы всегда отслеживаете, сколько bs стало четным или нечетным. States 0, 2 and 4 означает, что пришло четное число b. Таким образом, вы можете разделить этот DFA на две части по вертикали, где нижние состояния равны четным bs, а верхние состояния - нечетным.

Также String принимается, если нечетное b, следовательно, конечное состояние должно быть в одном из состояний в верхней части.

не только количество b является условием, но a должно быть не менее 2. Таким образом, вы можете разделить этот DFA по горизонтали на три части, где количество as равно 0 в state-0 and 1, as равно одному в state-2 and 3 и as равно 2 в state-4 and 5. После первых двух a в строке разрешено любое количество a, поэтому в состояниях q4 и q5 возникает цикл.

_{количество требуемых состояний равно шести, потому что 2 состояния для нечетных четных b и a s должно быть не менее 2, поэтому 3 состояния a=0, a=1, a=2, следовательно, 2*3 = 6}

Это делается с помощью продукта из двух автоматов.