На картинке ниже я пытаюсь понять, что именно принимает этот NFA.
Что меня смущает, так это прыжок на .q 0
Если введен , система переместится в и (состояние принятия)?q 0 q 1
Если введено , система переместится на и ?q 1 q 2
Переходит ли система только в (состояние принятия), если не вводится ничего (пустая строка)?
automata
finite-automata
nondeterminism
user3472798
источник
источник
Ответы:
Каждый раз, когда вы находитесь в состоянии с переходом , это означает, что вы автоматически находитесь в ОБА состояниях, чтобы упростить это для вас:ϵ
Если строка то ваши автоматы заканчиваются как в и вq 0 q 1ϵ q0 q1
Если ваша строка '0', она снова будет в иq 1q0 q1
Если ваша строка '1', это будет только в , потому что если вы смотрите с точки , у вас есть переход '1' к , но вы также должны посмотреть на случай, когда вы находитесь в ( если вы были в вы также всегда были в ), тогда нет перехода '1', поэтому этот альтернативный путь просто "умирает".q 0 q 2 q 1 q 0 q 1q2 q0 q2 q1 q0 q1
Просто взглянув на эти случаи, легко увидеть, что ваши автоматы принимают , и переходят от к , единственный способ достичь - это , так что это возобновляет ваши автоматы до , ,0 ∗ q 0 q 1 q 2 0 ∗ 11 ∗ 1 ϵ 0 ∗ 0 ∗ 11 ∗ 1ϵ 0∗ q0 q1 q2 0∗11∗1 ϵ 0∗ 0∗11∗1
Надеюсь, что это помогло вам, если у вас есть дальнейшие сомнения, просто спросите!
источник
В состоянии без чтения какого-либо ввода NFA одновременно остается в и (в альтернативном юниверсе, если хотите) также переходит в состояние . Это похоже на то, что произошло бы в NFA, который имел два перехода в разные состояния при вводе символа. В частности, ваш NFA принимает пустую строку, так как ни на одном входе он не может перейти в состояние принятия .q0 q0 q1 q1
Продолжая ваш пример, из состояния увидев вход , он будет использовать этот символ, оставаться в состоянии (цикл), а также переходить в состояние , тем самым принимая вход . В состоянии считывающем вход , NFA перейдет в состояние . Он также может не потреблять , переходить в состояние в другом юниверсе и застрять там (и не принимать, поскольку он не прочитал все входные данные), поскольку нет перехода от к .q0 0 q0 q1 0 q0 1 q2 1 q1 q1 1
Посмотрите, можете ли вы убедить себя, что язык, принятый этой машиной, обозначается регулярным выражением , т. Е. Любой строкой, состоящей из нуля или более с, за которыми не должно быть ничего или два или больше с.0∗+0∗11∗1 0 1
Кстати, есть алгоритм, который принимает NFA с -moves и производит эквивалентный NFA без -moves, который, я надеюсь, вы вскоре узнаете.ϵ ϵ
источник
Я пытался построить DFA для этого NFA
Поскольку каждый NFA имеет равный DFA, давайте построим DFA для данного NFA.M′
алфавит - то же самое
Текущее состояниеR∈P(Q)
Некоторые вычисляют на этом FSM
по крайней мере{ϵ,0∗}⊂L(M′)
Спасибо Дэвиду Ричерби
источник