Пример недетерминированного конечного автомата
Рисунок 4. 3. Пример недетерминированного конечного автомата.
Переход выполняется всякий раз при чтении входного символа. Заметим, что переходы могут быть недетерминированными. На Рисунок 4.3 видно, что если автомат находится в состоянии S1, и текущий входной символ равен а, то переход может осуществиться как в S1, так и в S2. Некоторые дуги помечены меткой пусто, обозначающей "пустой символ". Эти дуги соответствуют "спонтанным переходам" автомата. Такой переход называется спонтанным, потому что он выполняется без чтения входной цепочки. Наблюдатель, рассматривающий автомат как черный ящик, не сможет обнаружить, что произошел какой-либо переход.
Состояние S3 обведено двойной линией, это означает, что S3 - конечное состояние. Про автомат говорят, что он допускает входную цепочку, если в графе переходов существует путь, такой, что:
(1) он начинается в начальном состоянии,
(2) он оканчивается в конечном состоянии, и
(3) метки дуг, образующих этот путь, соответствуют полной входной цепочке.
Решать, какой из возможных переходов делать в каждый момент времени - исключительно внутреннее дело автомата. В частности, автомат сам решает, делать ли спонтанный переход, если он возможен в
