Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 4 стр.

}, -это событие, состоящее из пустого слова е и всевозможных слов вида: s, ss, и т.д., т.е.
{s}=e ∨ s ∨ ss ∨ sss ∨ ...
       В алгебре событий, при отсутствии круглых скобок изменяющих порядок действий,
установлен следующий приоритет операций в порядке убывания: итерация, конкатенация
и потом дизъюнкция. Регулярное событие это событие, которое можно получить из эле-
ментарных событий в результате применения к ним конечного числа раз основных опера-
ций алгебры событий.
       Теперь определим модель цифрового автомата - распознавателя, для которого будут
разрабатываться алгоритмы решения задач идентификации цепочек - образов [ 4 ]. Де-
терминированный конечный автомат - распознаватель (ДКА) будем рассматривать как
устройство, которое в каждый конкретный момент времени находится в одном из конеч-
ного множества состояний, и входной ленты (входная последовательность) состоящей из
клеток, которая просматривается слева направо блоком чтения этого устройства. Каждый
шаг алгоритма распознавания ДКА состоит из перехода в новое состояние, определяемое
его текущим состоянием и читаемым входным сигналом, и сдвига блока чтения на одну
клетку вправо. Оказывается, что любой язык представим регулярным выражением тогда и
только тогда, когда он допускается некоторым конечным автоматом.
       Если решается задача только обнаружения наличия цепочки - образа, то достаточно
модели одностороннего автомата, в которой на каждом шаге алгоритма блок чтения
может перемещаться на одну клетку только слева направо. Если же решается задача об-
наружения местоположения цепочки - образа, то необходимо использовать модель двух-
стороннего автомата, в которой блок чтения может перемещаться или слева направо
или справа налево. Лента, которую читает автомат, должна содержать два специальных
символа: "начало" (top) и "конец" (bottom), при достижении которых передвижение го-
ловки соответственно влево и вправо невозможно, о чем сообщается выработкой специ-
альных сигналов "достижение начала"(yt)/"достижение конца"(yb).
       Важным обобщением понятия ДКА является НДКА. Для каждого состояния и каж-
дого входного сигнала функция переходов НДКА имеет нуль или более вариантов выбора
следующего шага алгоритма. В [1,2] предлагается аналитический язык задания НДКА,
получивший название языка систем канонических уравнений и систем выходных функ-
ций (СКУ и СВФ). Там же предлагается способ перехода от РВАС к СКУ и СВФ. Эта
связка двух языков позволяет снять ограничения языка РВАС при формализации ниже
перечисленных задач идентификации. Например, хотя алгоритм идентификации задачи
типа "1" (смотри ниже) практически напрямую формализуется на языке РВАС, переход к
его программной или аппаратной реализации мягко говоря неочевиден.
       Основным достоинством языка СКУ и СВФ является то, что алгоритм записанный
на этом языке представляет готовое решение для программной или аппаратной реализа-
ции, и что самое главное, автором языка предложен простой и эффективный способ пере-
хода от РВАС к СКУ и СВФ. Алгоритм построения СКУ по регулярным выражениям ис-
ходной системы событий содержит следующие этапы:
    1) В каждом из регулярных выражений исходной системы событий, отмеченных соот-
   ветствующими выходными сигналами, выделяют параллельные ветви в отдельные ре-
   гулярные выражения. Получается система выражений, в каждом из которых в правой
   части (за исключением содержимого итерационных скобок) есть только операции
   сцепления и итерации


                                            4