Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Наше предложение вытекает теперь непосредственно из лемм 1 и 2.
15.1.3. Канонический гомоморфизм
Будем считать известным определение свободной группы с системой свободных образующих 91 (см. упражнение 2 из п. 15.1.10).
Пусть дан канонический гомоморфизм у. отображающий 33* на эту свободную группу:
Я—> 1, а —>-а, а' —»-а-1;
тогда из у if) = у if) следует, что / и f сокращаются до одного и того же несократимого слова.
Множество Y-1OK т- е- ядро гомоморфизма у. представляет собой множество слов, сократимых до E Это множество называют языком Дика, определенным над S3 = 91 U 91'; мы будем обозначать его через D*.
15.1.4. Ограниченные языки Дика
Если выполнять только сокращения пар аа', ЬЬ' и т. п., но не пар a'a, b'b, ..., то получается ограниченный язык Дика2).
') Точнее, из аХ ~ аУ следует X ~ У. Действительно, аХ ~ аУ влечет за собой а'аХ ~ а'аУ, но а'аХ ~ X, а'аУ ~ У. — Прим. ред.
г) Точнее, ограниченный язык Дика над алфавитом SB = Sl (J Sl' есть по определению множество тех слов (цепочек) в алфавите SB, которые переводятся в E последовательным вычеркиванием пар аа', ЬЬ', ,,, . — Прим ред. Г л XV. Дополнительные сведения о КС-языках
235
Как уже отмечалось (см. п. 1.3.2), ограниченные языки Дика хорошо известны в математике: достаточно интерпретировать буквы без штрихов как левые скобки, а буквы со штрихами — как соответствующие их правые скобки.
15.1.5. Языки Дика являются КС-языками
Интерпретация букв как скобок и ее «обобщение» на случай произвольных языков Дика делают очевидным тот факт, что языки Дика являются КС-языками.
Ограниченный язык Дика может быть порожден, например, следующей грамматикой:
S->SS
S-+aSa', bSb', ... S->aa', bb', ... Например, для слова (цепочки) abbaa'b'cc'bb'b'a' имеется вывод
abb аа' b' сс' bb' b' а'
Таким образом, построенная нами грамматика является неоднозначной. Рассмотрим теперь языки Дика более подробно с тем, 236
Часть III. Алгебраический подход
чтобы предложить для них однозначные грамматики, более согласованные с их структурой.
15.1.6. Разложение цепочек на Д-простые цепочки
Будем говорить, что цепочка d є D* является Д-простой (или простой по Дику), если никакое непустое начало цепочки d, отличное от самой d, не принадлежит D*1). Заменяя слово «начало» словом «конец», получим эквивалентное определение2).
Пример. Цепочка a'baa'bb'b'a является Д-простой; цепочка abb'a'bb' не является Д-простой.
Теорема. Всякая цепочка, принадлежащая языку Дика, единственным образом представимо как произведение (конкатенация) Д-простых цепочек.
Для Д-простой цепочки теорема очевидна. Пусть d не является Д-простой цепочкой; предположим, что она может быть разложена двумя разными способами:
d = hf2... k = SrIgr2 •¦¦ Внесли I/i I = |gi|, то fr = gi; сокращая, получим f2 •• -ft.=82 ••• g\i, после чего рассуждение можно повторить.
Если І/і I < IgrI I, ТО gl не является Д-простой цепочкой.
15.1.7. Структура Д-простых цепочек
Пусть цепочка g = xfy, где хну — буквы, является Д-простой. В ходе сокращения цепочки g буква х сокращается с у и не может сокращаться ни с какой другой буквой; действительно, в противном случае цепочка g имела бы непустое начало, принадлежащее языку Дика и отличное от самой g. Тем самым у «спарена» с х, и мы будем писать у = х.
Таким образом, цепочка / принадлежит языку Дика, и, следовательно, ее можно представить как произведение Д-простых цепочек:
/ = /1/2 • • • fm>
где /l имеет вид XifiXu причем Xi Ф X, поскольку в противном случае цепочка g не была бы Д-простой. Аналогично получаем: /2 = f'iXi, где X2 Ф X3), f3 = /а*з, где X3 Ф х, и т. д.
Обозначим через Dy множество всех Д-простых цепочек, начинающихся буквой у (и оканчивающихся буквой у).
') Началом, соответственно концом, цепочки X называется всякая цепочка Y, такая, что X представима в виде YZ, соответственно ZY —Прим. ред.
2) Действительно, если цепочка X є D* представима в виде YZ, где Y є D*, то Z є D* (иначе, если X = YZ и У сократимы до ?", то и Z сократимо до Е), и обратно. — Прим. ред.
3) Действительно, в противном случае цепочка XfiX2, являющаяся непустым началом g, совпадала бы с xfix и тем самым принадлежала бы языку Дика.— Прим ред. Г л XV. Дополнительные сведения о КС-языках
237
Мы можем теперь сказать, что всякая Д-простая цепочка имеет единственное представление вида
S = Xfl ... fmx,
где fi е Dxh Х{ Ф X, і = I, ..., m.
Пример. Цепочка ab'сс'baa'с'а!аса' записывается следую-щим образом:
a b'cc'b аа' с'а'ас а'.
Обозначим через D множество всех Д-простых цепочек. В силу теоремы о единственности разложения на Д-простые цепочки язык D* есть свободная полугруппа над D (этим объясняются используемые обозначения).
15.1.8. Однозначная грамматика, порождающая язык Дика
Построим для языка Дика однозначную КС-грамматику; она будет записана в виде системы уравнений.
Для простоты ограничимся алфавитом {a, a', b, Ь'}, что никак не отразится на общности наших рассуждений.
Введем нетерминальные символы Da, Da', Db, Dy, имеющие то же значение, что и в предыдущем пункте.
