4. Алгоритм Фельдмана и автоматные грамматики:

Рассмотрим следующую автоматную грамматику :

,

,

Для восстановления грамматики выберем следующие цепочки .

Алгоритм Фельдмана при длине остатка конструирует следующую грамматику:

Как видно, язык грамматики таков . Очевидно, он не совпадает с языком исходной автоматной грамматикой (например если подставить abacc).

Для получения исходной автоматной грамматики потребуется использовать следующий набор цепочек . Тогда алгоритмом будет сконструирована грамматика:

.

Легко убедиться, что данная грамматика является эквивалентной исходной грамматике , то есть порождает такой же язык. Аналогичного вывода можно достичь, если использовать длины остатка .

Таким образом, на результат восстановления грамматики влияет размер выборки и длина остатка

5. Алгоритм Фельдмана и контекстно-свободные грамматики:

Модификация алгоритма Фельдмана для конструирования контекстно-свободных грамматик может работать следующим образом.

Первоначально алгоритм выделяет из цепочек выборки фрагменты, которые могли быть образованы правилами КС-грамматик. Такие фрагменты обычно содержатся во многих цепочках и содержат более чем два символа.

На основе выделенных фрагментов создаются правила КС-грамматики, которые их порождают. Правила имеют вид где ; их множество . В цепочках выборки мы заменяем выбранные фрагменты некоторыми неиспользуемыми терминалами .

Для модифицированных цепочек по алгоритму Фельдмана строится автоматная грамматика (алгоритм теперь применяется на модифицированных «автоматных» цепочках, что и позволяет получить эффективную грамматику). В результате мы получаем автоматную грамматику с набором «контекстных» правил.

Остается:

• заменить введенные терминалы на соответствующие нетерминалы из правил ;

• каждое конечное правило из связать с построенной грамматикой переходом на некоторые терминалы или нетерминалы.

6. Пример

Рассмотрим работу модифицированного алгоритма на примере. Пусть выборка содержит цепочки .

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

Модифицируем исходное множество цепочек: . Применяем для него оригинальный алгоритм Фельдмана.

Получаем грамматику , где

После этого введем конструкции правил КС-грамматики :

Здесь правило является конечным, оно должно быть связано с построенной грамматикой посредством введения нового нетерминала .

В результате грамматика является контекстно-свободной.

ДЛЯ ЛЮБОЗНАТЕЛЬНЫХ

Постановка задачи:

Предположим, у нас имеются два класса образов w1 и w2 и пусть образы образы этих классов могут быть построены из признаков, принадлежащих некоторому конечному множеству. Назовем эти признаки терминалами и обозначим множество терминалов символом V_т .

В синтаксическом распознавании образов терминалы называются также непроизводными символами (элементами). Каждый образ может рассматриваться как цепочка или предложение, поскольку он составлен из терминалов множества V_T. Допустим, что существует грамматика G, такая, что порождаемый ею язык состоит из предложений (образов), принадлежащих исключительно одному из классов, скажем w1. Очевидно, что эта грамматика может быть использована в целях классификации образов, так как заданный образ неизвестной природы может быть отнесен к w1 если он является предложением языка L(G).В противном случае образ приписывается классу w2.

Например, бесконтекстная грамматика G = (Vn, Vт, P, S) при Vn= {S}, Vt= {a, b) и

множестве правил подстановки Р= {S->aaSb, S->aab} обладает способностью порождать лишь предложения, содержащие вдвое больше символов а, чем Ь. Если мы сформулируем гипотетическую задачу разбиения образов на два класса, причем объекты класса w1 — это цепочки вида aab, aaaabb и т. д., а объекты класса w2 содержат одинаковое число символов а и Ь (т. е. ab, aabb и т. д.), то очевидно, что классификация заданной цепочки производится простым определением того, может ли данная цепочка порождаться грамматикой G, рассмотренной выше. Если может, то объект принадлежит w1, если нет — он автоматически приписывается классу w2. Процедура, используемая для определения, является или не является цепочка предложением, грамматически правильным для данного языка, называется грамматическим разбором.

Постановка задачи по Фельдману можно сформулировать как:

• Дано: множество выборочных цепочек .

• Требуется: подвергнуть обработке с помощью адаптивного обучающегося алгоритма, на выходе которого воспроизводится грамматика , согласованная с данными цепочками.

• Т.е. множество цепочек является подмножеством языка , порождаемого грамматикой .

28