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

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

5
2) Для каждой параллельной ветви (если она заканчивается итерационной скобкой)
каждого из регулярных выражений системы событий выполняют операцию замены
итерационных скобок вспомогательными переменными, которые будут, играть роль
дополнительных входных сигналов.
3) Каждое регулярное выражение системы преобразуется в систему рекуррентных ре-
гулярных соотношений вида s
i
=s
j
z
k
, где s
j
событие заменяющее всю часть выражения
за исключением самого правого входного сигнала.
4) Если самый правый входной сигнал - вспомогательная переменная из п.2, то вы-
полняют ее обратную замену на итерационную скобку, которую затем раскрывают с
использованием следующего соотношения: если P=S{Q}, то P=S
∨
PQ.
5) Если содержимое раскрываемой итерации в п.4 не одноэлементное событие, а
сложное выражения включающее в том числе и внутренние итерационные скобки, то
для этого события повторяют все операции, предусмотренные в пунктах 1-5 до тех
пор, пока не будут раскрыты все итерационные скобки.
6) В итоге каждое полученное уравнение в правой части должно содержать сцепление
события и входного сигнала или дизъюнкцию таких сцеплений. В тех случаях, если в
процессе преобразований, в правых частях уравнений будут встречаться события без
входного сигнала, необходимо сделать подстановку вместо таких событий соответст-
вующих им выражений.
7) В итоге заменяя во всех уравнениях знаки конкатенации на знаки конъюнкции и,
вводя дискретное время, получают СКУ, в которой обозначения событий исходной
системы отмечаются соответствующими выходными сигналами.
Пример на построение СКУ и СВФ по регулярному выражению приведен далее в раз-
деле 1.3.
1.2 Формулировка задач распознавания цепочек - образов
Рассмотрим более детально формулировку задач распознавания цепочек - образов, в
том числе описываемых регулярными выражениями. Пусть дана входная цепочка-
последовательность следующего вида W=topw
1
w
2
... w
n
bottom ( w
i
- любой символ из ал-
фавита Z) и цепочка-образ, заданная регулярным выражением R=z
g
z
m
... z
n
. Надо найти
такой наименьший индекс j символа входной последовательности, что для некоторого i
подцепочка w
i
w
i+1
...w
j
, цепочки W принадлежит языку, представленному выражением R [
4 ].
В зависимости от того, какая цель преследуется в результате поиска можно выде-
лить следующие классы задач. Обнаружение факта наличия цепочки, и только. Напри-
  2) Для каждой параллельной ветви (если она заканчивается итерационной скобкой)
   каждого из регулярных выражений системы событий выполняют операцию замены
   итерационных скобок вспомогательными переменными, которые будут, играть роль
   дополнительных входных сигналов.

  3) Каждое регулярное выражение системы преобразуется в систему рекуррентных ре-
   гулярных соотношений вида si=sjzk, где sj событие заменяющее всю часть выражения
   за исключением самого правого входного сигнала.

  4) Если самый правый входной сигнал - вспомогательная переменная из п.2, то вы-
   полняют ее обратную замену на итерационную скобку, которую затем раскрывают с
   использованием следующего соотношения: если P=S{Q}, то P=S ∨ PQ.

  5) Если содержимое раскрываемой итерации в п.4 не одноэлементное событие, а
   сложное выражения включающее в том числе и внутренние итерационные скобки, то
   для этого события повторяют все операции, предусмотренные в пунктах 1-5 до тех
   пор, пока не будут раскрыты все итерационные скобки.

  6) В итоге каждое полученное уравнение в правой части должно содержать сцепление
   события и входного сигнала или дизъюнкцию таких сцеплений. В тех случаях, если в
   процессе преобразований, в правых частях уравнений будут встречаться события без
   входного сигнала, необходимо сделать подстановку вместо таких событий соответст-
   вующих им выражений.

  7) В итоге заменяя во всех уравнениях знаки конкатенации на знаки конъюнкции и,
   вводя дискретное время, получают СКУ, в которой обозначения событий исходной
   системы отмечаются соответствующими выходными сигналами.

  Пример на построение СКУ и СВФ по регулярному выражению приведен далее в раз-
деле 1.3.
             1.2 Формулировка задач распознавания цепочек - образов
     Рассмотрим более детально формулировку задач распознавания цепочек - образов, в
том числе описываемых регулярными выражениями. Пусть дана входная цепочка-
последовательность следующего вида W=topw1w2 ... wnbottom ( wi - любой символ из ал-
фавита Z) и цепочка-образ, заданная регулярным выражением R=zgzm ... zn. Надо найти
такой наименьший индекс j символа входной последовательности, что для некоторого i
подцепочка wiwi+1...wj, цепочки W принадлежит языку, представленному выражением R [
4 ].
     В зависимости от того, какая цель преследуется в результате поиска можно выде-
лить следующие классы задач. Обнаружение факта наличия цепочки, и только. Напри-



                                         5

Страницы