недетерминированный вопрос конечной автоматизации

Я кое-что изучаю и немного запутался в этом маленьком недетерминированном алгоритме, когда он обрабатывает 1. Я понимаю, что он разделится на бренд с q1, так как 0 или 1 перенаправят обратно, и что есть стрелка выхода к q2. равно 1, но зачем ему разбиваться на q3? Я чувствую, что неправильно понимаю (0, пустая строка), любое уточнение было бы здорово.

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

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


non-deterministic finite-automata
person jfisk    schedule 19.09.2011    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Пустая строка означает, что вы можете взять ее в любое время. В этом случае 1 приведет к q2 и, поскольку q2 имеет стрелку пустой строки к q3. Он также немедленно примет это без необходимости получения следующего бита ввода.

person flight    schedule 19.09.2011
comment
Ах хорошо. Если это так, то почему ветвь 4-й 1 вниз умирает в q2? - person jfisk; 19.09.2011
comment
... потому что нет стрелки, выходящей из q2 для входа 1, так что ветвь умирает - person Nemo; 19.09.2011
comment
Он начинается с q1, а затем получает вход 1. Он может перейти к q1, q2 или q3, а затем получить следующий вход. В этом случае переход к q2, получение следующего ввода и переход к q3 аналогичны переходу прямо к q3 и последующему получению ввода. По сути, он не показывает его, потому что это дубликат пути q3 рядом с ним. - person flight; 19.09.2011
comment
@Nemo Нет, он спрашивает, почему это не продолжается, поскольку я сказал, что вы можете взять пустую строку в любой момент. (Эээ... у меня мозг начинает болеть от всех этих размышлений) - person flight; 19.09.2011