Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
57"
3.1.8. Неоднозначность
Встав на наиболее общую точку зрения, мы будем считать два доказательства одной и той же теоремы различными, если они различаются либо входящими в них словами, либо порядком этих слов, либо и тем, и другим.
Теорема (выводимое из аксиомы слово или фраза) является неоднозначной, если для нее существует два различных доказательства (вывода).
Для приложений можно вводить различные — более сильные или более слабые — понятия неоднозначности.
Пример. С ситуацией неоднозначности слова мы встречались в примере 3 п. 3.1.5: к слову bbsb можно было прийти двумя путями. Вот еще один пример.
Пусть имеется алфавит {а, Ь, с, s}, аксиома 's' и следующие продукции:
• as ¦sb ¦asb ¦ с
(1) (2)
(3)
(4)
Теорема acb является неоднозначной. Действительно, она имеет два доказательства:
1) asb acb,
(2)
(IL
2) s -?- asb -?- acb.
(4).
§ 3.2. НОРМАЛЬНЫЕ СИСТЕМЫ
3.2.0. Нормальная система
Чтобы определить нормальную систему, необходимо задать . алфавит & = {аг 11 .. аксиому А;
... V нормальных продукций (схем продукций)
[G1P-^PG1] 1</<V}, где A, Gj и Gj — слова свободной полугруппы, порождаемой множеством її. 58
Часть /. Предварительные сведения из логики и алгебры
Пример. Пусть имеется нормальная система с алфавитом {а, Ь}, аксиомой 'а' и схемами продукций
аР-+ Pbba, b P-+Paba.
Пример доказательства: а -> bba -> baaba.
3.2.1. Каноническое соответствие между нормальной и полутуэвской системами
Для упрощения записи мы будем рассматривать систему с алфавитом из трех букв; легко, однако, видеть, что общность наших рассуждений нисколько от этого не страдает.
Итак, пусть имеется полутуэвская система (ST) *):
!алфавит: її = {а, Ь, с}, аксиома: А,
продукции: PGiQ-+ PGiQ, 1
Требуется построить по системе (ST) такую нормальную систему (N), которая имела бы ту же аксиому А и теоремы которой группировались бы в классы в соответствии с некоторым отношением эквивалентности; при этом теоремы системы (N) должны быть связаны с теоремами системы (ST) следующим образом: . всякая теорема системы (ST) является теоремой и в (N); •• всякая теорема системы (N) принадлежит некоторому классу эквивалентности, в котором имеется и некоторая теорема системы (ST).
Указанное соответствие между системами (ST) и (N) иллюстрируется следующей схемой: Гл. III. Комбинаторные системы
5»
Чтобы построить (N), мы продублируем алфавит системы (ST), введя в него буквы со штрихами: а', Ъ' и с'. Всякому слову Af, записанному в алфавите її, отвечает слово M', получаемое из Af добавлением штрихов ко всем вхождениям букв в Af; условимся, что E' = Е.
Теперь мы можем определить
алфавит: S = {а, Ь, с, а', Ь', с'}, аксиома: А, продукции трех типов: ^ 1) аР-*Ра' и аналогичные,
2) a'P-* Pa и аналогичные,
3) G1P-* PGi, 1<г<т.
Сопряженные слова. Заметим, что продукции типов (1) и (2) построенной нами системы (N) позволяют перебрасывать некоторую букву из начала слова в его конец, меняя при этом ее «штриховость» (если она имела штрих, он утрачивается; если штриха не было, он появляется).
Пусть и, V, w, ... — переменные, представляющие буквы алфавита 93, а u, V, w, ... — переменные, представляющие те же буквы, но с обратной «штриховостью». Возьмем, например, слово wuuv и будем поочередно применять к нему ту из продукций типа (1) или (2), которую удается применить. В результате получится циклический вывод:
wuuv <--
UUVW и V W й V W u й W й й V й й V W U V W и VWUU WUUV-
Таким образом, можно определить класс эквивалентности, состоящий из сопряженных слов. В частности, среди всех слов, сопряженных со словом М, есть и M'. Это можно усмотреть из вывода на приведенной выше схеме — для этого достаточно интерпретировать наличие (отсутствие) крышечки над буквой как наличие (отсутствие) штриха.
Все слова, сопряженные со словами из її*, и только эти слова, имеют форму PQ' или P'Q, где Р, Qe її*.
Такие слова мы назовем регулярными. 60
Часть /. Предварительные сведения из логики и алгебры
Прямое утверждение. Докажем, что всякая теорема по-лутуэвской системы (ST) является теоремой нормальной системы (N).
Лемма 1. Всякое слово, сопряженное с теоремой системы (N), есть теорема системы (N).
В самом деле, слова, сопряженные с теоремой, выводятся из нее посредством применения продукций системы (N).
Заметим, что доказываемое нами утверждение явным образом верно для аксиомы А, общей обеим системам. Поскольку все теоремы получаются из А, достаточно доказать, что свойство «быть теоремой системы (N)» сохраняется при применении продукций системы (ST).
Предположим, что теорема X системы (ST) является теоремой в (N). Для того чтобы X имела следствие в (ST), необходимо, чтобы X могла быть представлена в виде X = PGiQ: тогда из /Y непосредственно следует X = PGiQ.
Однако в силу леммы 1 слово GiQP', сопряженное с А", является теоремой (N). Применяя к GiQP' подходящую продукцию типа (3), мы можем получить слово QP'G'i, также являющееся теоремой (N). Это последнее слово сопряжено с PGiQ, которое поэтому (в силу леммы 1) есть теорема системы (N), что и требовалось доказать.
