Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Эти соотношения определяют отношение эквивалентности; мы знаем, что 33*/9ї — полугруппа с единицей.
Эта полугруппа является группой. В самом деле, для всякого слова Л можно найти слово A, такое, что
AA ~ AA ~ Е.
Для этого достаточно . взять слово A — обращение слова Л;
.. «инвертировать» штриховку в A (т. е. снять штрихи у тех букв, где они были, и поставить у тех, где их не было).
Пример. Для A = аЪа'Ъ'аЬЪ имеем
Л = bbab'a'ba, А = b'b'a'bab'a'.
Ясно, что элементом 33*/3t, обратным классу элемента Л, будет класс элемента A.
Покажем теперь, что группа 23*/9t изоморфна свободной группе, порождаемой множеством її, и определим канонический гомоморфизм, отображающий 55* на эту группу.
15.1.2. Представление произвольного класса из 33*/3ї
Будем называть слово несократимым, если в нем нет ни одного вхождения буквы X, смежного с вхождением буквы х'.
Пример. Слово aba'b'ab несократимо; слово abb'ab сократимо Пустое слово является несократимым.
Предложение. Всякий класс определенной выше эквивалентности содержит одно и только одно несократимое слово.Г л XV. Дополнительные сведения о КС-языках
233
Существование несократимого слова в каждом классе очевидно. Докажем его единственность.
Для этого покажем сначала, что справедлива
Лемма 1. Единственное несократимое слово, эквивалентное пустому слову, есть само пустое слово.
Будем говорить, что слова X И у смежные, если от одного из них к другому можно перейти однократным применением одного соотношения.
Выражение «слово А эквивалентно пустому слову Е» означает, что имеется последовательность слов Xq, Xi, ..., хп, такая, что X0 — = А, хп — E и каждое Xi смежно с Поскольку по этой последовательности можно двигаться и в обратном направлении, то, образуя все слова, смежные с Е, затем все слова, смежные с этими смежными, и т. д., мы обязательно на каком-то шаге получим А. Словами, смежными с Е, являются аа', а'а, bb' и т. д. Чтобы получить слова, смежные с этими последними, можно либо сокращать их, но тогда мы будем вновь получать Е, либо вставлять в любое место одно из слов аа', а'а, bb', b b.....
Вообще, строя слова, смежные с данными словами, следует «наращивать», а не сокращать, потому что любое сокращение возвращает нас к слову, уже получившемуся на одном из предыдущих тагов ').
') Точнее, всякое слово, эквивалентное Е, может быть получено из E одними вставками (без сокращений). Это утверждение, из которого немедленно вытекает лемма 1, может быть доказано следующим образом Пусть A0, ...
.., An—последовательность слов, в которой каждое следующее слово смежно с предыдущим, и при этом A0 = E Пусть при определяемом этой последовательностью способе перехода от E к А „ первое сокращение происходит на k-м шаге, т е. при получении Ah из Ah-\. Тогда либо Ah-\ = Xaa'Y, Ak = XY, либо то же с перестановкой а и а'\ можно ограничиться разбором первого случая Если данные («главные») вхождения а и а' были вставлены на одном шаге, этот шаг, так же как и k-н, можно было бы не делать, и мы получаем способ перекода от E к А п с меньшим числом сокращений. Пусть эти вхождения были вставлены на разных шагах. Тогда возможны три случая: 1) X = X^a1Xi, Y = = Y2aYu причем выделенное вхождение а' в X было вставлено вместе с «главным» вхождением а на і-м шаге, а выделенное вхождение а в Y — вместе с «главным» вхождением а' на ]¦ м. Пусть для определенности і < /. Тогда можно не делать
1 го и k-ro шагов, а все те вставки, в результате которых получается Y1 (все они делались после у-го шага), производить не правее вставленного на /-м шаге о', а левее В результате снова получаем способ перехода от E к An с меньшим числом вставок. 2) X = Х{аХ2а'Х3, причем выделенное вхождение а было вставлено вместе с «главным» вхождением а' на і-м шаге, а выделенное вхождение —вместе с «главным» вхождением а на /'-м, і < j. В этом случае можно опять-таки не делать 1-го и k-vo шагов, а те вставки, которые дают .X3 (они делались после J-го шага), делать не левее вставленного на J-м шаге а', а правее. 3) Случай, когда оба вхождения а' и а, парных «главным» вхождениям, находятся в Y, аналогичен предыдущему. — Прим.. ред234
Часть III. Алгебраический подход
Пример. Начиная со слова аа'ЬЬ' и вставляя аа' между аа' и ЬЬ', мы получим aa'aa'bb'. Если мы будем сокращать, как показано подчеркиванием: aa'aa'bb', то все равно вернемся к аа'ЬЬ'.
Из сказанного следует, что в классе слова E не существует непустых несократимых слов.
Теперь нам понадобится еще
Jl е м м а 2. Если бы существовали различные несократимые слова, эквивалентные друг другу, то существовали бы непустые несократимые слова, эквивалентные пустому слову.
Пусть А и В — несократимые и эквивалентные друг другу слова. Будем считать, что они начинаются с разных букв (в противном случае этого было бы легко добиться посредством сокращений)1):
A = XA1, В = у B1, X фу.
Ясно, что при данных условиях слово AB = A\X\yBi несократимо.
Но из А ~ В следует AB ~ AA ~ Е, что и требовалось доказать.