Преобразовать данный NFA

Мы можем использовать конструкцию подмножества или набора мощности, чтобы перейти от NFA к DFA, рассматривая подмножества состояний NFA как потенциальные состояния соответствующего DFA. Начальное состояние нашего DFA будет {q0}, что означает, что только q0 может быть достигнуто до чтения любого ввода. После чтения a из {q0} мы можем достичь q2, используя a, а затем снова q0, выполнив лямбда-переход. Следовательно, f({q0}, a) = {q0, q2}. Прочитав b в {q0}, мы можем перейти только к q1; поэтому f({q0}, b) = {q1}.

Мы ввели два новых состояния, {q0, q2} и {q1}, в DFA, для которых нам нужны переходы. Недолгое размышление покажет, что {q0, q2} имеет точно такие же переходы, что и {q0}. На входе a q1 может перейти к q1, q2 или q0 (через q2); на вход b он может попасть в q2 или q0 (через q2). Итак, f({q1}, a) = {q0, q1, q2} и f({q1}, b) = {q0, q2}.

Мы уже видели {q0, q2} и знаем его переходы. Однако теперь нам нужны переходы для {q0, q1, q2}. Кажется, что на входе a все состояния NFA могут быть достигнуты из некоторого состояния; то же самое верно для входа b. Итак, f({q0, q1, q2}, a) = {q0, q1, q2} и f({q0, q1, q2}, b) = {q0, q1, q2}.

Мы не вводили никаких новых состояний на этой итерации, поэтому у нас есть все состояния, которые нам могут понадобиться в DFA. Наш DFA выглядит так:

q            s    q'
{q0}         a    {q0, q2}
{q0}         b    {q1}
{q0, q2}     a    {q0, q2}
{q0, q2}     b    {q1}
{q1}         a    {q0, q1, q2}
{q1}         b    {q0, q2}
{q0, q1, q2} a    {q0, q1, q2}
{q0, q1, q2} b    {q0, q1, q2}

Все состояния, кроме {q1}, являются допускающими, поскольку все они содержат допускающее состояние q0 из NFA. Теперь, прежде чем свернуть этот DFA, давайте переименуем состояния:

qA = {q0}
qB = {q0, q2}
qC = {q1}
qD = {q0, q1, q2}

Мы можем итеративно вычеркнуть пары состояний, которые не могут быть объединены следующим образом:

   qA,qB    qA,qC    qA,qD    qB,qC    qB,qD    qC,qD
   --------------------------------------------------
1.          xxxxx             xxxxx             xxxxx
Reason: qC cannot be combined with others since it is
        not accepting and the others are

2.                   xxxxx             xxxxxx
Reason: f((qA, qD), b) and f((qB, qD), b) equal (qC, qD)
        which was crossed off during the last iteration.

qA,qB cannot be crossed off, so these states can be
combined in a minimal DFA.

Полученный минимальный DFA:

q            s    q'
qAB          a    qAB
qAB          b    qC
qC           a    qD
qC           b    qAB
qD           a    qD
qD           b    qD