Поиск недетерминированного языка конечных автоматов

Во-первых, я отвечу на вопрос по-своему. Затем я обращусь к вашему преобразованию в детерминированный конечный автомат.

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

(q1) = (q2)a + e
(q2) = (q1) + (q3)(a + b)
(q3) = (q1)a + (q3)b

Мы хотим решить, что приводит к состоянию принятия, поэтому давайте сначала устраним непринятие:

(q1) = (q2)a + e
(q2) = (q2)a + e + (q3)(a + b)
(q3) = (q2)aa + a + (q3)b

Чтобы исключить (q3), мы можем использовать правило (x) = r + (x)s ‹=> (x) = rs* и затем заменить:

(q1) = (q2)a + e
(q3) = ((q2)aa + e)b*
(q2) = (q2)a + e + ((q2)aa + a)b*(a + b)
     = (q2)a + e + (q2)aab*(a + b) + ab*(a + b)
     = (q2)[a + aab*(a + b)] + [e + ab*(a + b)]
     = (e + ab*(a + b))(a + aab*(a + b))*
     = (e + ab*(a + b))(a(e + ab*(a + b)))*

Регулярное выражение, которое мы восстанавливаем, в основном описывает это:

Доберитесь до q2, либо выполнив пустой переход, либо пройдя q3; затем вернитесь к q2, перейдя к q1 и повторив первую часть. Вы можете делать это столько раз, сколько хотите.

Как вы пишете систему?

1. начальное состояние может быть достигнуто e
2. если есть переход из состояния q в состояние q' по выражению r, то q' = (q)r
3. если состояние может быть достигнуто более чем одним способом, используйте + и укажите все способы

Чтобы определить конечный автомат, рассмотрите каждое подмножество состояний и добавляйте переходы по ходу дела. Начнем с подмножества {q1}, состоящего только из начального состояния.

  /------------------------------------\
  |                               __   |
  V                              /  \  |
{q1} -a-> {q1,q3} -a-> {q1,q2,q3}   a  |
 |           |             |     ^__/  |
 b           b             b           |
 |     __    |             |           |
 V    /  V   V             |           |
{ }   b   {q2,q3} <--------/           |
 ^    \__/      \                      |
 |               \-a->{q1,q2}-----a----/
 |                     |               
 \----------b----------/

Правила добавления состояний и переходов:

1. Всегда добавляйте начальное состояние {qi}
2. Для каждого состояния {q1,q2,...,qn} и каждого символа x во входном алфавите добавьте переход из {q1,q2,...,qn} в {q1',q2',..., qn'} на x, где q1', q2',..., qn' достижимы из q1, q2,..., qn, используя ровно один x (и, возможно, несколько e-переходов)
3. Если состояния {q1',q2',...,qn'} еще нет в вашем автомате, добавьте его и повторите этот процесс для этого состояния.
4. Повторяйте вышеописанное до тех пор, пока не будут добавлены все необходимые состояния, и все состояния будут иметь переходы для каждого символа во входном алфавите.

Примечание: в приведенном выше автомате я не показывал переходы в мертвое состояние { }. Все переходы, возникающие в мертвом состоянии, заканчиваются в мертвом состоянии.

Мой {q1} аналогичен вашему самому верхнему (ОК). Мой { } аналогичен вашему HOLE. Мое {q1,q3} аналогично вашему НЕ. Мой {q2,q3} аналогичен вашему крайнему правому OK.

Однако мой {q1,q2,q3} НЕ аналогичен вашему самому нижнему OK. Чтобы ваш был похож на мой, добавьте переход от самого нижнего ОК к крайнему правому ОК на символе b.

Обратите внимание, что мой {q1,q2} избыточен и эквивалентен моему {q1}; все переходы из {q1,q2} такие же, как и из {q1}. Действительно, из-за e-перехода из q1 в q2 я должен был сделать {q1,q2} начальным состоянием, но как бы то ни было - вы поняли.

Причина, по которой ваш DFA не может быть правильным, заключается в том, что в NFA всегда есть шанс «взорвать его» и оказаться в яме. В своем автомате можно дойти до самого нижнего ОК и тогда ставиться.