Epsilon закрытие и автоматы

Question

Мне кажется, я не совсем понимаю концепцию эпсилон-переходов при определении языка недетерминированных автоматов.Например, в этих автоматах:

Язык: 'Двойная последовательность a или двойная последовательность b, где существует вероятность baa sequence '.

Но слово a тоже принадлежит автоматам, не так ли?(также слово b, aaa и т. д.)

Answer 1

ε-переход - это просто импровизированный переход, который не потребляет никакого ввода.

Когда вы находитесь в состоянии, которое имеет исходящие ε-переходы , это все равно что находиться во всех них, пока автомат не сделает что-то наблюдаемое, отсюда недетерминизм.Множество таких состояний является ε-замыканием состояния.

В соответствии с компоновкой вы можете иметь произвольное количество префиксов baa, за которыми следует произвольное количество a с или bs.Итак:

• пусто
• baa
• baabaa
• a
• aa
• ba
• abab
• baabab
• ...