Я работаю через Sipser Book (2-е издание) и наткнулся на этот пример, который я не понимаю. В книге говорится, что этот NFA принимает пустую строку .
Может ли кто-нибудь объяснить мне, почему это так?
Насколько я понимаю, перейдет к который не является состоянием принятия.
regular-languages
finite-automata
nondeterminism
Выпуклый леопард
источник
источник
Ответы:
Вы путаетеε с письмом. Это не письмо! Это просто пустая строка.
Давайте рассмотрим немного более общую модель, «слово-НФА». Слово-NFA похоже на NFA, но каждый переход помечен произвольным словом. Мы говорим, что слово NFA принимает слововес если существует переход от начального состояния к конечному состоянию, так что, если мы объединяем метки ребер по ходу, мы получаем вес . В символах слово-NFA принимает вес если существует последовательность переходов
Q0→вес1Q1→вес2Q2→вес3⋯ →весNQN
источник