Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 198 стр.

выражением тогда и только тогда, когда он допускается некоторым
конечным автоматом.
      Если решается задача только обнаружения наличия цепочки - образа,
то достаточно модели одностороннего автомата, в которой на каждом
шаге алгоритма блок чтения может перемещаться на одну клетку только
слева направо. Если же решается задача обнаружения местоположения
цепочки - образа, то необходимо использовать модель двухстороннего
автомата, в которой блок чтения может перемещаться или слева направо
или справа налево. Лента, которую читает автомат, должна содержать два
специальных символа: «начало» - zt (top) и «конец» - zb(bottom), при
достижении которых передвижение головки соответственно влево и вправо
невозможно, о чем сообщается выработкой специальных сигналов
"достижение начала"(yt)/"достижение конца"(yb).
      Важным обобщением понятия ДА является НДА. Для каждого события
(состояния) и каждого входного сигнала функция переходов НДА имеет нуль
или более вариантов выбора следующего шага алгоритма. При этом
необходимо иметь в виду, что для построения систем распознавания языков,
в определении НДА должен быть указан состав заключительных событий
(состояний), определяющих все допустимые слова языка (вместо состава
выходных сигналов НДА, используемых при построении управляющих
систем). Аналитический язык задания НДА, получивший название языка
систем канонических уравнений и систем выходных функций (СКУ и СВФ)
совместно с алгоритмом перехода от РВАС к СКУ и СВФ, позволяют снять
имеющиеся ограничения языка РВАС при формализации ниже
перечисленных задач идентификации. Следует отметить, что автор языка
предложил (глава 4) простой и эффективный способ перехода от РВАС к
СКУ и СВФ.
      Кроме того, хотя алгоритм идентификации задачи, например, типа "1"
(смотри ниже) практически напрямую формализуется на языке РВАС,
переход к его программной или аппаратной реализации неочевиден. В то же
время алгоритм, записанный на языке СКУ и СВФ, представляет готовое
решение для программной или аппаратной реализации.
        7.1. Формализация задач распознавания цепочек -
                         образов
      7.1.1. Формулировка задач распознавания цепочек-образов
      Рассмотрим более детально формулировку задач распознавания
цепочек-образов. Пусть дана цепочка-последовательность следующего вида
M  zt z  ,1 z,2  z m , j  z  ,n zb (где z m, j любой символ из алфавита [Z], у
которого введен дополнительный второй индекс j, определяющий
порядковый номер этого символа в последовательности M) и цепочка—образ
p, заданная регулярным выражением в том же алфавите. Требуется найти
такой наименьший индекс j символа входной последовательности M, что для
                                                                                 198