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

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

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 85 86 87 88 89 90 < 91 > 92 93 94 95 96 97 .. 101 >> Следующая


1) S соответствует ориентированному топологическому сегменту, который мы назовем потенциальным и будем изображать так:

2) aSS отвечает ориентированному топологическому треугольнику, имеющему одну реальную сторону а и две потенциальные стороны ShS. Это соответствие иллюстрируется следующей схемой:

3) Замена S на aSS (при выполнении первого правила) означает: построить треугольник aSS, такой, что его реальная сторона а совпадает — с учетом ориентации! — с соответствующей потенциальной стороной S, а он сам находится вне многоугольника, уже построенного к этому моменту.

Нетрудно доказать по индукции, что это последнее условие всегда может быть соблюдено: тем самым применение правил не связано никакими контекстными ограничениями. 268

Часть III. Алгебраический подход

Пример. Приведем дерево вывода цепочки в нашей грамматике и триангулированный многоугольник, являющийся переводом этой цепочки.

4) Правило S-*~b означает замену потенциальной стороны S реальной стороной Ь. Это заключительное правило замыкает многоугольник с той стороны, где оно применяется.

Ясно, что всякой терминальной цепочке соответствует правильно триангулированный многоугольник. Все а, кроме первого, представляют диагонали, а все b — стороны.

Легко доказать по индукции, что общее число всех Swb равно увеличенному на единицу числу всех а.

С другой стороны, треугольников столько же, сколько имеется вхождений символа а. Таким образом, мы получили классический результат: число треугольников равно числу сторон минус два или числу триангулирующих диагоналей плюс единица.

I

S

аа Та S ss Гл. XVI. Алгебраические языки

299

Пример. Цепочка

a aba b b b

І і

I I

1 I 2 I 3 4 5 I I

і-і

1 2

представляет пятиугольник, разбитый двумя диагоналями на три треугольника.

Заметим, что пометить и ориентировать одну сторону многоугольника — это то же самое, что пометить все его вершины. Следовательно, любая терминальная цепочка, содержащая п вхождений а, соответствует одной триангуляции некоторого (п + 2) -угольника с помеченными вершинами.

Две разные цепочки, содержащие п вхождений а, отвечают двум разным триангуляциям.

Любая триангуляция может бьпь получена описанным выше способом.

Пример. Взяв пятиугольник ABCDE и выделив в нем сторону AB, мы получим следующие соответствия:

D 270

Часть III. Алгебраический подход

Для того чтобы обеспечить порождение (без повторений) последовательности всех триангулированных многоугольников, достаточно образовать последовательность цепочек, порождаемых грамматикой

I S-+b, S^aSS I,

т. е. решить уравнение, содержащее некоммутирующие члены:

5 = ft + aSS.

В результате соответствующих выкладок (приводившихся в гл. XI) получается следующий некоммутативный ряд:

(s): ft + abb + ababb + aabbb + aabbabb + ....

Если нас интересует только подсчет числа возможных разбиений многоугольника, то, поскольку число сторон многоугольника равно числу вхождений в цепочку символа а, увеличенному на два, ясно, что число возможных триангуляции (п + 2)-угольника равно коэффициенту при хп в коммутативном ряде, полученном из (s) заменой а на х и b на 1.

Достаточно рассмотреть гомоморфизм

( а —> л:,

{ 5 у, ху = ух,

Функция у удовлетворяет уравнению

i/ = l + XiА

Имеем

у=\+х + 2х2 + Бхг+ ....

Пример. Для пятиугольника (п + 2 = 5) надо взять коэффициент при X3, т. е. 5.

16.5.3. Упражнения

1. Пусть имеется треугольник ABC. Взяв внутри него некоторую точку и соединив ее с вершинами, мы разобьем треугольник Гл. XVI. Алгебраические языки

271

на три других, каждый из которых может аналогичным образом быть разбит на три треугольника и т. д.

Исследовать эту тернарную триангуляцию. Использовать грамматику

Т-> TTT T->t

2. Исследовать разбиение 2п-угольника на четырехугольники с помощью непересекающихся диагоналей. Приложение ТРАНСФОРМАЦИОННЫЕ ГРАММАТИКИ

§ 1. формальные грамматики и естественные языки

Многие понятия, рассматривавшиеся в этой книге, возникли при исследовании естественных языков1). Например:

— В логике были формализованы определенные операции над предложениями обычного языка: «неверно, что ...»: ~I, «... или... ...»: V, «... и ...»: Д, «если ..., то...»: гэ, «... равносильно...»: ^ и т. п. (вместо многоточий должны подставляться предложения).

— Возникновение понятия марковской цепи, соответствующего понятию А-языка, было связано со статистическим исследованием последовательностей гласных и согласных в литературном тексте.

— Понятие формальной грамматики, введенное Н. Хомским, возникло в результате многочисленных усилий, направленных на создание строгих и абсолютно эксплицитных описаний некоторых грамматических закономерностей естественного языка (Хэррис [1946—1951]).

Цель современной лингвистики состоит в построении таких описаний естественных языков, которые могли бы быть полностью формализованы с помощью абстрактного автомата, формальной грамматики или какой-либо алгебраической конструкции. Такое требование к лингвистическим описаниям представляется совершенно обоснованным с теоретической точки зрения: ведь лингвист хочет познать и описать не что иное, как механизмы, посредством которых люди строят и понимают высказывания. Эти механизмы, образующие языковую интуицию носителей данного языка, описываются традиционной грамматикой весьма несовершенно.
Предыдущая << 1 .. 85 86 87 88 89 90 < 91 > 92 93 94 95 96 97 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed