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

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

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 2 3 4 5 < 6 > 7 8 9 10 11 12 .. 101 >> Следующая


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'.

Цепочка А называется симметричной, если она совпадает со своим обращением; например: В = 'шалаш', С = 'тортскофенефок-строт'.

Рассмотрим следующее ассоциативное исчисление: її = {а, Ь}; аа~Е; ЬЬ~Е.

(Отметим попутно, что такие исчисления называются нилыготент-ными.)

Сократить слово А в этом исчислении — значит образовать новое слово В, смежное с А, причем В должно быть короче А.

Взяв некоторое слово за исходное, мы можем путем последовательных сокращений образовать ряд слов, который приведет нас к несократимому слову; оно может быть, в частности, пустым.

Пример. Возьмем в качестве исходного слова
Предыдущая << 1 .. 2 3 4 5 < 6 > 7 8 9 10 11 12 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed