Иллюстрированный самоучитель по введению в экспертные системы



             

Канонические системы



Порождения — это в действительности грамматические правила манипулирования строками символов и потому их иногда называют правилами переписывания (rewrite rules). Пост изучал свойства систем правил, базирующихся на порождениях, которые он назвал каноническими системами [Post, 1943]. Каноническая система — это разновидность формальной системы, основанной на следующих компонентах:

  • алфавит А, из символов которого формируются строки;

  • некоторое множество строк, которые рассматриваются как аксиомы,

  • множества порождений в форме

    а1$1 ... am$m->b1$'1...bn$'1...bn$'n.

    где

    (I) каждое ai и bi; есть фиксированная строка;

    (II) а1 и am, часто есть нуль;

    (III) некоторые или все из ai или bi могут представлять собой нуль;

    (IV) каждое $i является переменной строкой, которая также может быть нулем;

    (V) каждое $i заменяется определенным $'i .

    Определение канонической системы, возможно, станет более понятным, если привести пример. Пусть А — алфавит {а, b, с}, а аксиомы суть:

    а, b, с, аа, bb, cc.

    Тогда следующие порождения сгенерируют все палиндромы, базирующиеся на этом алфавите, приняв за отправную точку имеющиеся аксиомы:

    (Р1)$->а$a (Р2) $ -> ab$ab (РЗ) $ -> с$с.

    Более того, в данном случае можно проследить применение правил, которые должны привести к росту определенного палиндрома. Например, чтобы сгенерировать bacab, нужно применить Р1 к аксиоме с, а затем Р2 — к результату. Другими словами, приняв с в качестве аксиомы, можно вывести из нее теорему аса и добавить ее к имеющимся аксиомам. Затем из аса можно вывести новую теорему bacab. Обратите внимание, что эта последовательность порождений не обладает свойством коммутативности, т.е. если применять те же правила, но в ином порядке, получится совсем другой результат. Например, если к аксиоме с применить сначала правило Р2, а затем Р1, то получим abcba.

    На первый взгляд канонические системы довольно тривиальны. Все, что можно сделать в рамках такой системы, — преобразовать одну строку символов в другую.


    Содержание  Назад  Вперед