Искусственный интеллект

Каждая упорядоченная пара (v, w) называется нарождающим правилом. Порождающее правило обычно обозначается v -> w. Из определения порождающего правила следует, что w не может быть пустой последо¬вательностью. Формальной грамматикой называют четверку: G = (N, A, Р, S), где Р является непустым конечным множеством порождающих правил, а S — специальный непустой символ, называемый начальным нетерминальным символом. Н. Хомским предложена классификация формальных фамматик, состоящая из четырех типов: 0, 1, 2 и 3, в зависимости от типа порождающих правил. Классификация Хомского (/(v) означает длину последовательности v) приведена в табл. 5.1. Из этой таблицы следует, что любая автоматная грамматика является одновременно контекстно-свободной, любая контекстно-свободная — контекстно-зависимой, любая контекстно-зависимая — грамматикой типа 0. Последовательность w*выводима из последовательности v*c помощью правила v -> w, если последовательность v* содержит подпоследовательность v, замена которой на и> дает w*. Вывод последовательности и>*из последовательности v* с помощью правилаgобозначим v* => w*. Последовательность w*выводима из v*c помощью правил gl, gl, ..., gk, g(k+l), если существует множество