Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Остальные правила позволяют переходить от некоторых классов слов к конкретным словам этих классов.
') Подчеркнем, что выражение Ph, равно как и выражения Gn, Gv, Art,— единый символ, т. е. одна буква вспомогательного алфавита, а не цепочка букв, ср. идентификаторы в Алголе. — Прим. перев. 54
Часть /. Предварительные сведения из логики и алгебры
Ниже изображена в виде дерева процедура построения фразы L'enfant cueille un abricot «Ребенок срывает абрикос» (возможность представить эту процедуру посредством дерева объясняется теми же соображениями, что и в предыдущем примере):
Аналогичным образом мы могли бы построить фразы Un enfant mange l'abricot «Ребенок ест абрикос», L'abricot cueille l'enfant «Абрикос срывает ребенка» и т. п. Первая из этих фраз — правильная и вполне банальная французская фраза, вторая же могла бы фигурировав в сказке вроде «Алисы в стране чудес».
Пример 3. Алфавит системы — {s, b, s}; аксиома — 's'; продукции
S —> sb, (1) S-* С, (2)
ebb -*bbs (3)
являются полутуэвскими.
Из-за продукции (3) вывод в данной системе уже нельзя представить в виде дерева, как в предыдущих примерах. Однако он может быть изображен посредством ориентированного графа, устроенного следующим образом: на каждой дуге графа поме- Гл. 111. Комбинаторные системы
55"
щается номер примененной продукции; ребра с (1) направлены налево, ребра с (2) — направо, а ребра с (3) — вертикально вниз.
s
Заметим, что к слову bbsb ведут из s два пути1).
3.1.6. Доказательство теорем
Пусть имеется комбинаторная система Г и конечная последовательность 2 слов
X1, X2, ..., Xm,
где Xi — выделенное слово, т. е. аксиома системы Г, а каждое слово Xj, 1 < / ^ ш, есть следствие ИЗ слова Xj-i относительно некоторой продукции из Г.
Мы будем называть последовательность 2 доказательством в Г, а последнее слово последовательности 2 — теоремой в Г.
Переход от слова Xj—i к слову Xj называется шагом доказательства. (М. Дэвис называет «шагом» каждое слово Xj, что представляется менее естественным.)
Вместо «доказательство теоремы» мы будем говорить также «вывод слова» (или «вывод фразы», если базовое множество названо «словарем») 2).
') Данный граф в отличие от деревьев предыдущих примеров представляет не один вывод, а все множество выводов в данной системе; представлениями отдельных выводов являются пути в графе. В частности, наличие двух путей из S в bbsb означает, что слово bbsb имеет два различных вывода Заметим еще, что так можно представить множество выводов любой комбинаторной системы. — Прим. ред.
2) Введенное здесь понятие доказательства может рассматриваться как частный случай (для комбинаторных систем) общего понятия вывода, определенного на стр. 47. Действительно, описанное там дерево в случае комбинаторной системы будет деревом без ветвления (поскольку каждое правило имеет теперь лишь одну посылку), т. е. линейной последовательностью. —• Прим. ред. 56 Часть /. Предварительные сведения из логики и алгебры
Иногда приходится доказывать некоторое утверждение обо всех словах данной системы или обо всех словах определенного класса. В тех случаях, когда возможно неоднозначное понимание, подобное утверждение будет в отличие от теорем системы называться мета-теоремой; язык, на котором формулируется метатеорема, является по отношению к рассматриваемой системе метаязыком.
Пример 1. Вернемся к примеру 1 из п. 3.1.5. Алфавит системы— {а, Ь), аксиома —'s', продукции— s—*ab, s—*asb. Мы доказали теорему aaaabbbb и привели дерево доказательства.
Утверждение «Всякое выводимое из аксиомы слово системы, не содержащее буквы s, представимо как конкатенация слова, состоящего из вхождений буквы а, со словом той же длины, состоящим из вхождений буквы Ь» есть метатеорема.
Пример 2. В примере 3 из п. 3.1.5 слово 'bbsb' является теоремой, имеющей, как это видно из графа, иллюстрирующего пример, два разных доказательства.
Утверждение «В данной системе существует бесконечно много теорем, каждая из которых имеет два доказательства» есть метатеорема.
3.1.7. Моногенные системы
Комбинаторная система Г называется моногенной, если к любой ее теореме может быть применено не более одной продукции. Иначе говоря, в моногеннои системе Г невозможна теорема X, такая, что
. X представима двумя разными способами — как GPHQK и как G'P'H'Q'K', причем
.. в Г имеются две продукции с левыми частями GPHQK и G'P'H'Q'K' соответственно.
Пример 1. Система примера 1 из п. 3.1.5 не является моногенной, потому что к S можно применить две разные продукции, иначе говоря, из S можно получить два разных следствия, а именно ab и asb.
П р и м е р 2. Система с алфавитом {а, Ь, с), вспомогательным алфавитом {s, t, и), аксиомой 's' и продукциями
s-+atb, atb —> aaub, и-+ с
является моногенной и позволяет получить лишь конечное число теорем.
Пример 3. Система с алфавитом {a, b,s}, аксиомой 's' и продукцией s—*asb является моногенной и позволяет получить беско-лечное число теорем. Гл. 111. Комбинаторные системы
