Конвертировать данный NFA - PullRequest
Новая
       67

Конвертировать данный NFA

1 голос
/ 22 мая 2019

Вопрос) Σ = {a, b} и NFA даны на следующем рисунке:

  1. Используя процедуру NFA в DFA, конвертируйте данный NFA в DFA.
  2. Используяпроцедура уменьшения, минимизировать состояния в DFA
    enter image description here

Я сделал таблицу переходов для nfa и dfa, но застрял, не зная, где должен q2перейти к q0 или создать новое состояние, называя его q4

1 Ответ

0 голосов
/ 22 мая 2019

Мы можем использовать конструкцию подмножества или powerset для перехода от 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 могут быть достигнуты из некоторого состояния; то же самое верно для ввода б. Итак, 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
...