Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Обратное утверждение. Всякая теорема системы (N) является регулярным словом, сопряженным с некоторой теоремой системы (ST).
Будем действовать аналогично предыдущему. Аксиома А системы (N) является регулярным словом, сопряженным с некоторой теоремой системы (ST), а именно с самим собой. Поэтому достаточно доказать, что оба свойства (регулярность и сопряженность с некоторой теоремой системы (ST)) сохраняются при применении продукций системы (N).
Сохранение указанных свойств очевидно для продукций типов (1) и (2); рассмотрим продукции типа (3).
Предположим, что теорема GiP регулярна и сопряжена с некоторой теоремой системы (ST). Так как Gi фЕ, из регулярности GiP следует, что она может быть записана в виде GiP\Pi, где Pi и P2— слова в алфавите системы (ST). Единственное сопряженное с GiP слово в алфавите системы (ST)—это P2GiPi-, из нашего предположения вытекает, что P2GiPi^ теорема (ST). Отсюда следует, что PzGiPi — также теорема (ST); однако P2GiPі сопряжена со словом PiP2G';, которое является регулярным.
Итак, мы показали, что слово PGu полученное из С;Р посредством продукции типа (3) системы (N), сохраняет регулярность Гл. 111. Комбинаторные системы
61"
и сопряженность с некоторой теоремой (ST). Доказательство закончено.
Резюме. Пусть имеется полутуэвская система с алфавитом {а, Ь, с, ...}. Мы умеем поставить ей в соответствие нормальную систему с алфавитом {a, a',b,b', с, с', ...}, такую, что множество ее теорем, не содержащих штрихованных букв, совпадает со мно-' жеством теорем исходной полутуэвской системы.
§ 3.3. УПРАЖНЕНИЯ
1. Дана система с алфавитом її = {а,Ь,с}, аксиомой 'а' и проекциями a-*b, Ь-*с и с—*а.
Является ли эта система моногенной?
Является ли теорема 'с' неоднозначной?
Исключается ли неоднозначность моногенностью?
2. В примере п. 3.1.8 слово 'acb' неоднозначно из-за возможных ветвлений при построении вывода из 's'. Рассмотрим систему с алфавитом її = {a, b,s], аксиомой 's' и продукциями s—* ab и S-+asb. Является ли она моногенной? Получаются ли в ней неоднозначные теоремы?
Является ли наличие ветвления достаточным услов-ием для неоднозначности?
3. Дана система, имеющая продукции вида а-*а и Ь-*Е. Основываясь на этом конкретном примере, подвергнуть критике предложенное нами весьма общее определение неоднозначности. Подвергнуть его критике также с другой точки зрения, используя пример системы
f її = {Л, В, С, Ь, с} Г =I аксиома: А
{ продукции: А-у ВС, B-*b, C-*с.
4. Построить способом, предложенным в п. 3.2.1, нормальную :истему для полутуэвской системы
(Sf) =
її={а, Ь, с) аксиома: 'с'
продукция: PcQ-* PacbQ.
§ 3.4. НЕЗАВИСИМОСТЬ ОТ АЛФАВИТА
Известно, что буквы всякого алфавита могут быть закодированы с помощью букв другого алфавита меньшей мощности. Алфавит Морзе, позволяющий кодировать любые алфавиты, содер- 62
Часть /. Предварительные сведения из логики и алгебры
жит всего три элементарных символа: точка, тире, пробел. При одних способах кодирования пробел представляется специальным символом, при других он получается «сам собой».
В электронных вычислительных машинах используется двоичный код; с помощью слов, состоящих из п вхождений двоичных символов, можно закодировать 2п букв. Специальный символ для пробела не нужен благодаря делению машинной памяти на ячейки.
3.4.1. Двоичное кодирование
Ясно, что для любой комбинаторной системы (5) можно построить эквивалентную систему (S+) с алфавитом {0, 1}. Вот один из возможных способов построения такой системы.
Пусть Я = {аь ..., а„} есть алфавит системы (5). Положим а+= 4000 ... 01'; иначе, а+ = '10,+1Г. ' Ї+Г
Слову M = Oii ... aip мы поставим в соответствие слово
M+= att ... afp, а пустому слову E— пустое слово E+. Таким образом, полугруппа Я* отображается на некоторое подмножество M+ множества {0, 1}*; это отображение взаимно однозначно. Более точно, если дано слово в алфавите {0, 1}, то мы умеем
• узнать, принадлежит ли оно М+\
.. в случае, если оно принадлежит M+, найти единственное слово в M, являющееся его прообразом.
Будем говорить, что некоторое слово в алфавите {0, 1} является правильно построенным, если у него есть прообраз в Я*.
3.4.2. Построение системы S+
Если (S) имеет аксиому А и продукции
GlPHiQKi GiPHlQKt І і = 1, ¦ • •. m,
то в качестве аксиомы и продукций для (S+) мы возьмем соответственно A+ и
Gf PHfQKt GtPHtQKt I i=\.....m.
Предложение 1. Если M — теорема системы (S), то M+ — теорема системы (S+).
В самом деле, если Mi, ..., Mq, M есть доказательство M
в (S), то Mt.....Mq, M+ есть доказательство M+ в (S+), что
и требовалось доказать.
Предложение 2. Всякая теорема системы (S+) является правильно построенным словом.
Аксиома системы (S+) обладает этим свойством, и продукции системы (S+) сохраняют его, что и требовалось доказать. Гл. 111. Комбинаторные системы
63"
Предложение 3. Всякая теорема системы (S+) имеет своим прообразом некоторую теорему системы (S).
Возьмем произвольную теорему системы (S+). Поскольку она является правильно построенным словом, она имеет вид M+ при M є її*. Точно так же обстоит дело со всеми теоремами, фигурирующими в ее доказательстве. При этом, если некоторая теорема В системы (S+) получается из теоремы А системы (S+) с помощью некоторой продукции этой системы, то прообраз В получается из прообраза Л с помощью соответствующей продукции системы (S). Поэтому доказательство теоремы M+ в (S+) дает доказательство теоремы M в (S), что и требовалось доказать.
