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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

197
Глава 7. Проектирование алгоритмов для задач
идентификации языков
Задачи идентификации языков, реализуемые цифровым автоматом-
распознавателем, имеют очень широкое применение. В частности,
идентификация цепочек символов входит как составная часть во многие
задачи, связанные с редактированием текстов, поиском данных и символьной
обработкой. Многие программы редактирования текстов разрешают
пользователю задавать различные типы замен в тексте. Например,
пользователю необходимо заменить какое-то слово другим словом во всем
тексте или его части. Чтобы выполнить такое действие, программа
редактирования текста должна суметь найти вхождение слова и определить
его местоположение. Некоторые искусные редактирующие программы
разрешают пользователю в качестве множества заменяемых цепочек
символов указывать регулярное множество. Например, пользователь может
поставить задачу: «Заменить [R] в тексте M пустой цепочкой», имея в виду,
что в M следует стереть пару квадратных скобок и символы между ними,
представляющие выражение R.
Подобные задачи решаются в антивирусных программах. Например,
для обнаружения «простых» вирусов необходимо найти последовательность
байт (сигнатуру вирусов) в зараженном файле. При обнаружении
«полиморфных» вирусов обнаружение сигнатуры входит как одна из
составляющих технологии их поиска.
В типичной задаче идентификации цепочек -образов - задаются
входная последовательность M (например, символов или пронумерованные
фрагменты графических файлов и т.п.) и множество цепочек-образов [p
1
, p
2
,
... p
n
]. Требуется найти либо хотя бы одно вхождение какой-то цепочки-
образа, либо m из n (1
m<n), либо вхождения всех n цепочек-образов в M.
При этом множество цепочек-образов часто является регулярным
множеством, которое можно задать регулярным выражением алгебры
событий. Ниже будут показаны приемы решения такого рода задач,
основанные на использовании языка регулярных выражений алгебры
событий (РВАС) и модели недетерминированного конечного автомата
(НДА).
Модель конечного детерминированного цифрового автомата (ДА)-
распознавателя, для которого будут разрабатываться алгоритмы решения
задач идентификации цепочек-образов, будем рассматривать как устройство,
которое в каждый дискретный момент времени находится в одном из
конечного множества состояний, и входной ленты (входная
последовательность) состоящей из клеток, которая просматривается слева
направо блоком чтения этого устройства. Каждый шаг алгоритма
распознавания ДА состоит из перехода в новое состояние, определяемое его
текущим состоянием и читаемым входным сигналом, и сдвига блока чтения
на одну клетку вправо. Доказано, что любой язык представим регулярным 
  Глава 7. Проектирование алгоритмов для задач
             идентификации языков
         Задачи идентификации языков, реализуемые цифровым автоматом-
распознавателем, имеют очень широкое применение. В частности,
идентификация цепочек символов входит как составная часть во многие
задачи, связанные с редактированием текстов, поиском данных и символьной
обработкой. Многие программы редактирования текстов разрешают
пользователю задавать различные типы замен в тексте. Например,
пользователю необходимо заменить какое-то слово другим словом во всем
тексте или его части. Чтобы выполнить такое действие, программа
редактирования текста должна суметь найти вхождение слова и определить
его местоположение. Некоторые искусные редактирующие программы
разрешают пользователю в качестве множества заменяемых цепочек
символов указывать регулярное множество. Например, пользователь может
поставить задачу: «Заменить [R] в тексте M пустой цепочкой», имея в виду,
что в M следует стереть пару квадратных скобок и символы между ними,
представляющие выражение R.
         Подобные задачи решаются в антивирусных программах. Например,
для обнаружения «простых» вирусов необходимо найти последовательность
байт (сигнатуру вирусов) в зараженном файле. При обнаружении
«полиморфных» вирусов обнаружение сигнатуры входит как одна из
составляющих технологии их поиска.
         В типичной задаче идентификации цепочек -образов - задаются
входная последовательность M (например, символов или пронумерованные
фрагменты графических файлов и т.п.) и множество цепочек-образов [p1, p2,
... pn]. Требуется найти либо хотя бы одно вхождение какой-то цепочки-
образа, либо m из n (1  m

Страницы