Как NFA использует эпсилон-переходы?

12

На картинке ниже я пытаюсь понять, что именно принимает этот NFA.

введите описание изображения здесь

Что меня смущает, так это прыжок на .q 0ϵq0

  • Если введен , система переместится в и (состояние принятия)?q 0 q 10q0 q1

  • Если введено , система переместится на и ?q 1 q 21q1q2

  • Переходит ли система только в (состояние принятия), если не вводится ничего (пустая строка)?q1

user3472798
источник
2
Вернитесь к определениям: NFA принимает слово, если какое-либо вычисление для него принимает. NFA сами по себе не являются «алгоритмами» в смысле DFA.
Рафаэль

Ответы:

10

Каждый раз, когда вы находитесь в состоянии с переходом , это означает, что вы автоматически находитесь в ОБА состояниях, чтобы упростить это для вас:ϵ

Если строка то ваши автоматы заканчиваются как в и вq 0 q 1ϵq0q1

Если ваша строка '0', она снова будет в иq 1q0q1

Если ваша строка '1', это будет только в , потому что если вы смотрите с точки , у вас есть переход '1' к , но вы также должны посмотреть на случай, когда вы находитесь в ( если вы были в вы также всегда были в ), тогда нет перехода '1', поэтому этот альтернативный путь просто "умирает".q 0 q 2 q 1 q 0 q 1q2q0q2q1q0q1

Просто взглянув на эти случаи, легко увидеть, что ваши автоматы принимают , и переходят от к , единственный способ достичь - это , так что это возобновляет ваши автоматы до , ,0 q 0 q 1 q 2 0 11 1 ϵ 0 0 11 1ϵ0q0q1q20111ϵ00111

Надеюсь, что это помогло вам, если у вас есть дальнейшие сомнения, просто спросите!

H_DANILO
источник
7
«это означает, что вы автоматически находитесь в ОБАХ состояниях», - я не думаю, что это полезная интуиция, то есть она неправильно представляет недетерминизм.
Рафаэль
Почему это неправильно? Что ж, по определению дельта по недетерминизму, вы получаете набор состояний вместо 1 правильно? Это может означать только то, что вы находитесь в обоих штатах.
H_DANILO
Это продвигает идею, что недетерминированные машины «пробуют все решения параллельно». Это не то, что происходит, если говорить алгоритмически. Недетерминизм - это описательный формализм, а не алгоритмическая техника.
Рафаэль
Я попытался объяснить это понятным образом, так как он изо всех сил пытается понять принципы недетерминизма теоретическим путем
H_DANILO
@Raphael Какая интуиция, на ваш взгляд, была бы более полезной?
Андрей Портной
6

В состоянии без чтения какого-либо ввода NFA одновременно остается в и (в альтернативном юниверсе, если хотите) также переходит в состояние . Это похоже на то, что произошло бы в NFA, который имел два перехода в разные состояния при вводе символа. В частности, ваш NFA принимает пустую строку, так как ни на одном входе он не может перейти в состояние принятия .q0q0q1q1

Продолжая ваш пример, из состояния увидев вход , он будет использовать этот символ, оставаться в состоянии (цикл), а также переходить в состояние , тем самым принимая вход . В состоянии считывающем вход , NFA перейдет в состояние . Он также может не потреблять , переходить в состояние в другом юниверсе и застрять там (и не принимать, поскольку он не прочитал все входные данные), поскольку нет перехода от к .q00q0q10q01q21q1q11

Посмотрите, можете ли вы убедить себя, что язык, принятый этой машиной, обозначается регулярным выражением , т. Е. Любой строкой, состоящей из нуля или более с, за которыми не должно быть ничего или два или больше с.0+011101


Кстати, есть алгоритм, который принимает NFA с -moves и производит эквивалентный NFA без -moves, который, я надеюсь, вы вскоре узнаете.ϵϵ

Рик Декер
источник
-1

Я пытался построить DFA для этого NFA

- набор алфавитов

QНабор состояний

σ(Q×(ϵ))P(Q) функцию состояния

q0=q0

FQ,F={q0}

Поскольку каждый NFA имеет равный DFA, давайте построим DFA для данного NFA.M

алфавит - то же самое

Q=P(Q) - состояния

Текущее состояниеRP(Q)

E(R) - замыкание эпсилона возвращает набор состояний, достижимых через ноль или более - соединений для каждогоϵrR

σ(R,a)=rRE(σ(r,a)) -переходы

q0=E({q0})

F=P(Q)÷F

Некоторые вычисляют на этом FSM

1. ϵ на входе: начальное состояние включает поэтому FSM принимаетq0=E({q0})={q0,q1}q1ϵ

2. 0 на входе: поэтому ФСМ принимаетσ({q0,q1},0)=E(σ(q0,0))E(σ(q1,0))={q0,q1}{}={q0,q1}0

по крайней мере{ϵ,0}L(M)

Спасибо Дэвиду Ричерби

OrangeFish
источник
Спасибо, что поблагодарили меня, но я не понимаю, как это отвечает на вопрос. Вы не определили, на каком языке принимает аппарат, и не ответили ни на один из трех маркированных вопросов.
Дэвид Ричерби
1) когда ввод (пустая строка), состояние FSM равно 2) когда ввод равен или даже состояние FSM равно обеим темам начальных вопросов, не так ли? { д 0 , д 1 } 0 0 * { д 0 , д 1 }ϵ{q0,q1}00{q0,q1}
OrangeFish