Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 79

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 84 85 .. 101 >> Следующая


Эти соотношения определяют отношение эквивалентности; мы знаем, что 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 ~ Е, что и требовалось доказать.
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 84 85 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed