Теория автоматов. - 8 стр.

                                  Рис. 5                         Рис. 6




       Здесь начальное состояние 1, а заключительное F. Слово считается недо-
пустимым, если в результате реакции на него автомат не остановится в заклю-
чительном состоянии или если будет подан запрещенный (для данного состоя-
ния) входной сигнал. Например, воздействие входного слова ab на автомат вы-
зовет переход в состояние 2 по букве a , но в этом состоянии не определен пере-
ход по букве b , следовательно, слово ab недопустимо. Если считать пустое (не
содержащее ни одной буквы) слово допустимым, то можно еще более упростить
частичный автомат, объединив начальное и заключительное состояния (рис.6).

       3.Одним из наиболее широко используемых на практике типов распо-
знающих автоматов является частичный недетерминированный автомат. Неде-
терминизм проявляется в том, что из одного состояния по одному и тому же
входному сигналу возможны переходы в различные состояния, т.е. функция пе-
реходов заменяется отношением переходов. Недетерминированный автомат
(рис.7) принимает, например, слова ab, aa, bb, bba и т.д. здесь начальное со-
стояние A, а заключительное -F.
                                                  Рис. 7




      Таблица переходов данного автомата будет иметь вид табл.13.
                                   Таблица 13

                   A        B              C   F
           a      B,C                      F
           b       B        C,F


      Пустые клеточки говорят о том, что автомат частичный, а наличие сразу
нескольких букв в одной клеточке – о том, что автомат недетерминированный.
Для таких автоматов обычно предпочитают использовать не табличное и не