5.8. Языки и грамматики

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

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

5.8.1. Формальные грамматики

Назовем некоторое множество А, состоящее из элементов а, терминальным алфавитом, а его элементы терминалами. Введем также конечное непустое множество символов которые назовем нетерминалами. Множества и А не пересекаются. Объединение этих множеств обозначим

символом V. Элементы множества А будем по-прежнему обозначать строчными символами а, а элементы множества заглавными буквами. Множество всех последовательностей в алфавите V обозначим У. Если к множеству У добавить пустой символ, то получим множество Наконец, множество упорядоченных пар где является элементом множества элементом множества У, обозначим символом.

Каждая упорядоченная пара называется порождающим провалом. Порождающее правило обычно обозначается Из определения порождающего правила следует, что не может быть пустой последовательностью.

Формальной грамматикой называют четверку:

где Р является непустым конечным множеством порождающих правил, специальный непустой символ, называемый начальным нетерминальным символом. Н. Хомским предложена классификация формальных грамматик, состоящая из четырех типов: 0, 1, 2 и 3, в зависимости от типа порождающих правил. Классификация Хомского означает длину последовательности приведена в табл. 5.1.

Из этой таблицы следует, что любая автоматная грамматика является одновременно контекстно-свободной, любая контекстно-свободная — контекстно-зависимой, любая контекстно-зависимая — грамматикой типа 0. Последовательность выводима из последовательности помощью правила и», если последовательность содержит подпоследовательность замена которой на дает Вывод последовательности из последовательности с помощью правила обозначим Последовательность выводима из помощью правил если существует множество

Таблица 5.1

последовательностей таких, что

5.8.2. Языки

Язык порождаемый грамматикой является множеством всех последовательностей а множества А, которые могут быть выведены из начального нетерминального символа с помощью правил грамматики Пример. Дана автоматная грамматика С:

Язык, порождаемый этой грамматикой имеет вид

Здесь означает любую последовательность из идущих подряд символов за которыми следует единственный символ

Пример. Дана контекстно-свободная грамматика

Порождаемый язык

Пример. Контекстно-зависимая грамматика

Порождаемый язык