Недетерминированные конечные автоматы | Пример SIPSER 1.16

9

Я работаю через Sipser Book (2-е издание) и наткнулся на этот пример, который я не понимаю. В книге говорится, что этот NFA принимает пустую строку ε .

Может ли кто-нибудь объяснить мне, почему это так?

Насколько я понимаю, ε перейдет к Q3 который не является состоянием принятия.

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

Выпуклый леопард
источник
1
Это классический вопрос об использовании в NFA. Вот вопрос о том же примере, что означает входная строка epsilon? , Есть также вопрос значения ε в NFA-ε? и как NFA использует эпсилон-переходы? ε
Джон Л.
Спасибо за исчерпывающие ссылки - я думаю, что получил это сейчас.
выпуклый леопард

Ответы:

10

Вы путаете ε с письмом. Это не письмо! Это просто пустая строка.

Давайте рассмотрим немного более общую модель, «слово-НФА». Слово-NFA похоже на NFA, но каждый переход помечен произвольным словом. Мы говорим, что слово NFA принимает слово вес если существует переход от начального состояния к конечному состоянию, так что, если мы объединяем метки ребер по ходу, мы получаем вес . В символах слово-NFA принимает вес если существует последовательность переходов

Q0вес1Q1вес2Q2вес3весNQN

  1. Q0
  2. QN - это конечное состояние (также называемое принимающим состоянием).
  3. Qя-1весяQя
  4. весзнак равновес1...весN .

εε (т. Слова длиной не более 1). Обычно мы также требуем, чтобы было уникальное начальное состояние.

ε

Q0εQ1εεQN
Q0QNεNзнак равно0

Юваль Фильмус
источник
εQ1Q1Q1Q3Q1Q1ε
1
Да, это хорошее описание.
Юваль