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

Question

Я студент второго курса и изучаю информатику, и нам дают недетерминированный конечный автомат и спрашивают, какие слова он принимает.

Я попытался упростить его до детерминированного конечного автомата и в итоге получил следующее:

Я предположил, что это делаетне принимать ни одного слова в формате b * или a или a (b + ab * a) *, не могу понять, что общего между ними и какими словами оно принимает, я так понял, это не имеет отношения ко всемуword, только в начале, потому что если слово начинается с aa, оно может иметь любую комбинацию a и b и не имеет значения, будет ли оно принято.

будет очень признателен за помощь.

Answer 1

Сначала я отвечу на вопрос по-своему. Затем я расскажу о вашем преобразовании в детерминированный конечный автомат.

Мы можем написать набор уравнений и решить для 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. Начальное состояние может быть достигнуто с помощью
2. если в выражении r происходит переход из состояния q в состояние q ', то 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 (и, возможно, несколько электронных переходов)
3. Если состояния {q1 ', q2', ..., qn '} еще нет в вашем автомате, добавьте его и повторите этот процесс для этого состояния
4. Повторяйте выше, пока все необходимые состояния не будут добавлены и все состояния имеют переходы для каждого символа во входном алфавите.

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

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

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

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

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