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

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

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

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

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


non-deterministic finite-automata
person Nick    schedule 26.09.2018    source источник
comment
Все ваши примеры являются DFA (и тривиально NFA). Ваш первый пример неверен, потому что он принимает строки вне языка (например, aab). Ваши второй и третий примеры почти правильные, но не минимальные. Ни один DFA не принимает пустую строку, которая есть в языке. Возможен минимальный DFA с 3 состояниями (или 4 с явным мертвым состоянием). Состояния {q1, q2, q3}, q1 являются начальным и принимающим состояниями. Переходы: q1,a,q2, q1,b,q3, q2,b,q1, q3,a,q1.   -  person Welbog    schedule 26.09.2018

Ответы (1)


arrow_upward
1
arrow_downward

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

Вот NFA (q0 — начальное состояние и единственное принимающее состояние):

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

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

person Patrick87    schedule 09.10.2018