Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
3) Независимо от того, что понимается под значком — абстрактная буква или представляющая ее конкретная. — Прим ред,18
Часть /. Предварительные сведения из логики и алгебры
также необходимо различать графическое слово и то, что оно обозначает: известно, что слово «собака» не кусается.
Необходимо также различать букву «а», выступающую в роли базового элемента, и «а» как однобуквенное слово (союз «а»), как, например, в предложении «Мари ест апельсин, а Жан стрижет ногти».
Напротив, в теориях, где рассматриваются исключительно формальные свойства слов, безотносительно к какому бы то ни было смыслу, различать букву и однобуквенное слово, образованное этой буквой, незачем. Именно так обстоит дело в алгебраической теории свободных полугрупп.
§ 1.2. ОПЕРАЦИИ НАД СЛОВАМИ
1.2.1. Соотношения Туэ
Используемый в последующем изложении конкретный алфавит будет состоять из малых кириллических и латинских букв; слова будут обозначаться заглавными латинскими буквами, пустое слово — буквой Е.
Слово 1картошка'') содержит два вхождения слова 'ка': первое является началом слова 'картошка', второе — его концом. Слово 'банан' содержит два смежных вхождения слова 'ан'. Соответствующие понятия нетрудно определить в общем виде.
Пусть P и Q — два разных слова (любое из них может быть пустым). Предположим, что некоторое слово А содержит вхождение слова P и потому представимо в виде
А = XPY.
Такому слову А можно поставить в соответствие слово В, полученное из А подстановкой вхождения Q вместо вхождения Р.
Пример. Если P — слово 'ара', a Q — слово 'ло', то слову 'парад' соответствует слово 'плод'.
В этой главе мы будем рассматривать случай, когда, имея право замещать любое вхождение P вхождением Q, мы в то же время имеем право поступать и наоборот: замещать любое вхождение Q вхождением Р.
Тогда мы будем писать
я-Q; (1)
в предыдущем примере:
'ара' ~ 'ло'.
Между словами могут иметь место одновременно несколько соотношений типа (1); например:
'ара' ~ 'ло'ад'
') В оригинале здесь и ниже в качестве примеров используются французские словз, которые мы заменили подходящими русскими — Прим. перед.Гл. I. Слова (цепочки). Полугруппы. Языки
19
Подобные соотношения, называемые соотношениями Туэ (по имени впервые исследовавшего их норвежского математика), приводят к так называемым ассоциативным исчислениям.
Если слово В получается из слова А однократным применением одного соотношения, мы будем говорить, что А и В являются смежными-, ясно, что в таком случае А тоже получается из В применением одного соотношения.
Так, в нашем примере
'парк' является смежным с 'парад',
'парад' является смежным с 'плод', однако 'парк' не является смежным с 'плод'.
Чтобы получить транзитивное отношение, необходимо допустить несколько последовательных применений соотношений типа P~Q. Сформулируем строгое определение.
Определение. Пусть її — некоторый алфавит и R:Pi~ -—- Qi, ..., Pn ~ Qn — система соотношений Туэ. Тогда мы будем говорить, что слово B0 соотносимо со словом Bp, если существует последовательность слов B0, ..., Bp, таких, что Bi является смежным с 1 для 1 = 1, ..., р.
Условимся, кроме того, считать, что любое СЛОВО соотносимо с самим собой. Тогда соотносимость будет отношением эквивалентности. Это позволяет нам, следуя существующей традиции, называть соотносимые слова эквивалентными. Так, в нашем примере слово 'парк' эквивалентно слову 'плод'. Отношение эквивалентности мы будем обозначать знаком «~» и писать: 'парк'~'плод' и т. п.
Теперь мы можем сформулировать следующую теорему (ее доказательство представляется очевидным):
Теорема. Для любых слов Xu Y из A ^ В следует XAY ^ ~ XBY.
1.2.2. Проблема эквивалентности (слов)
Пусть имеется ассоциативное исчисление, заданное алфавитом її и соотношениями
Л-Qi, ..., Pn-Qn-
Туэ сформулировал следующую фундаментальную проблему, известную под названием «проблемы эквивалентности»:
Для произвольной пары слов установить, являются они эквивалентными или нет.
1.2.3. Несколько примеров
Прежде всего мы дадим два определения, которые в дальнейшем не раз будут нам полезны.20
Часть /. Предварительные сведения из логики и алгебры
Цепочка A называется обращением (зеркальным образом) цепочки А, если A состоит в точности из тех же вхождений, что и А, но взятых в обратном порядке, например:
А = 'ток', A = 'кот' или А = 'roma', A = 'amor'.
Цепочка А называется симметричной, если она совпадает со своим обращением; например: В = 'шалаш', С = 'тортскофенефок-строт'.
Рассмотрим следующее ассоциативное исчисление: її = {а, Ь}; аа~Е; ЬЬ~Е.
(Отметим попутно, что такие исчисления называются нилыготент-ными.)
Сократить слово А в этом исчислении — значит образовать новое слово В, смежное с А, причем В должно быть короче А.
Взяв некоторое слово за исходное, мы можем путем последовательных сокращений образовать ряд слов, который приведет нас к несократимому слову; оно может быть, в частности, пустым.
Пример. Возьмем в качестве исходного слова