9.5. Выбор типа языка

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

5.1.2. Грамматика будет основана на словаре Здесь это словарь терминальных символов, или слов, которыми мы будем пользоваться. Для обозначения элементов мы будем пользоваться буквами греческого пли латинского алфавита, и в некоторых случаях — словами естественного языка. В этих последних случаях не следует забывать, что эти слова нужно рассматривать как абстрактные понятия, а не подмножество естественного языка.

Словарь нетерминальных символов состоит из синтаксических переменных, или состояний. Они будут обозначаться числами , где это окончательное состояние. Условимся считать 1 начальным состоянием.

5.1.3. Продукции (правила) в всегда можно выразить в канонической форме:

Продукцию (9.5.1) следует читать как «состояние переходит в состояние при записи терминального символа Иногда будет удобнее считать в (9.5.1) конечной цепочкой символов, но это не ограничит возможностей грамматики.

5.1.4. Как и в гл. 8 второго тома, мы будем предполагать, что грамматика сведена к детерминированной форме, так что любые две продукции в вида

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

В (9.5.3) мы разложили предложение на последовательные продукции

5.1.5. Множество конечных цепочек, полученных выше указанным образом, представляет собой язык, порождаемый грамматикой т. е.

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

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

5.2. Эквивалентно язык может быть представлен конечным автоматом, который мы будем часто изображать в виде диаграммы. Чтобы уточнить обозначения, рассмотрим конечный автомат, диаграмма конструкции которого представлена на рис. 9.5.1.

Словари соответствующей грамматики - это

а продукции перечислены в табл. 9.5.1.

Грамматика, очевидно, является детерминированной. Она порождает, например, предложения, которые можно представить следующим образом:

или фразы вида

5.3. Еще один эквивалентный способ представления языков конечных состояний (или автоматных языков) это через регулярные выражения формальной логики. Такие выражения строятся при помощи конкатенации, конечного повторения (обозначаемого звездочкой), объединения и скобок, указывающих порядок «выполнения».

Язык, порождаемый диаграммой автомата на рис. 9.5.1, можно, например, представить в следующем виде:

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

Рис. 9.5.1

Таблица 9.5.1 (см. скан)

5.4.1. Для последующего крайне важно то обстоятельство, что языки конечных состояний, так же как и многие другие формальные языки, можно рассматривать как регулярные комбинаторные структуры (см. разд. 2.4 и 3.2).

Тогда образующие будут представлены продукциями из (но не словами!). У них показатель входной связи будет представлен состоянием в (9.5.1), т. е. исходным состоянием, а показатель выходной связи — через т. е. результирующим состоянием. Далее, имеем «равенство» и «линейный».

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

5.4.2. Строго говоря, такая алгебра изображений представляет не только но и все грамматически правильные фразы. Если нам нужно ограничиться только то требуются еще две образующие. Одна — это у которой и показатель выходной связи равен 1, а другая — это у которой и показатель входной связи равен будет алгеброй изображений, состоящей из всех изображений в у которых тип соединения будет «линейным» при дополнительном ограничении, согласно которому выходная арность должна быть равной нулю. Алгебра появится в следующем разделе в качестве вторичной алгебры изображений в семантических отношениях.