Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
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, мы получим следующие соответствия:
D270
Часть 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]).
Цель современной лингвистики состоит в построении таких описаний естественных языков, которые могли бы быть полностью формализованы с помощью абстрактного автомата, формальной грамматики или какой-либо алгебраической конструкции. Такое требование к лингвистическим описаниям представляется совершенно обоснованным с теоретической точки зрения: ведь лингвист хочет познать и описать не что иное, как механизмы, посредством которых люди строят и понимают высказывания. Эти механизмы, образующие языковую интуицию носителей данного языка, описываются традиционной грамматикой весьма несовершенно.