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

Question

Такое ощущение, что это должно быть проще, чем есть, но у меня проблема с этим.Вот что спрашивается:

Создайте NFA для следующего языка L = {ab, ba} *.Итак, я понимаю, что у меня может быть любая комбинация ab или ba в строке, но мне нужно мертвое состояние, если, скажем, я получаю два a подряд или оно просто начинается заново?Вот два графика, которые у меня есть:

Являются ли эти из них правильными?И поскольку они являются NFA против DFA, нужно ли где-нибудь здесь лямбда-ребро?

Редактировать: Правильно ли будет этот третий, потому что мне нужны два конечных состояния?

Answer 1

Если вы делаете NFA, вам не нужны мертвые состояния;Вы можете просто позволить NFA потерпеть крах.DFA, вероятно, действительно нужны мертвые состояния для полноты, в зависимости от ваших определений.

Вот NFA (q0 - исходное состояние и единственное принимающее состояние):

         b
      +------+
      |      |
      V  a   |    
  +->q0 ---> q1
  |   |
a |   | b
  |   V
  +--q2

Чтобы сделатьэто DFA, вы можете добавить мертвое состояние q3 и сделать все переходы, не определенные выше, прекратить в q3.