Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Ш. 9. Пусть S — множество всех систем составляющих, согласованных с деревом (X; -*?), и для Си С2 е S запись С!=фС2 означает, что Ci с С2 и не существует системы C'eS такой, что Ci с С' <± С2. Показать, что длина любого максимального пути в графе (S; =ф) (такой путь, вообще говоря, не один) равна сумме уменьшенных на единицу ширин кустов невисячих узлов дерева {Х-,->-).
312 СИСТЕМЫ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЯ ПОДЧИНЕНИЯ [П. 1
ГП. 10. Показать, что бинарная система составляющих, согласованная с деревом (X;-*), тогда и только Тогда единственна, когда для каждого узла этого дерева все подчиненные ему узлы расположены по одну сторону от него.
ГП. 11. Показать, что высота дерева подчинения, согласованного с системой составляющих, не превосходит высоты этой системы.
П1.12. Показать, что система составляющих С и дерево подчинения {Х\ -*-) тогда и только тогда согласованы, когда: а) группы зависимости всех узлов дерева (X;-*?) являются составляющими системы С; б) каждая составляющая системы С совпадает с множеством узлов некоторого поддерева дерева (Х\ -*•).
ГП. 13. Показать, что объединение множества подформул (в обычном смысле) произвольной формулы F исчисления предикатов (как в «скобочной», так и в бесскобочной записи) с множеством вхождений в F элементарных символов является системой составляющих для F.
ГП. 14. Назовем системы составляющих С и С| цепочек х и Х\ подобными, если изображающие их скобочные последовательности совпадают.
а) Сформулировать определение подобия, не упоминая о скобочных или иных изображениях.
б) Показать, что если F — формула исчисления предикатов в «скобочной» записи и Fi — та же формула в бесскобочной записи, то описанные в упражнении П1. 13 системы составляющих цепочек F и Ft подобны.
ГП. 15. Показать, что если дерево подчинения (Х\ -*?) связано с иерархизованной системой составляющих (С, С') цепочки х, а — точка цепочки х и В0 В\ :э ... гэ В, = {а} — все составляющие, для которых а служит главной точкой (так что В0 — группа зависимости узла а), то ширина куста узла а в дереве (Х;-+) равна (/о — 1)+...+(/(_! — 1), где h — ширина куста составляющей Sj.
Замечание. Если s0 — степень составляющей В0, то $о < t ^ (/о — 1)+...+(/(_! — 1), так что ширина куста а не может быть меньше s0. Поэтому степень системы С не превосходит ширины дерева (Х;-+).
П1.16. Построить «естественные» системы составляющих для предложений:
а) Века пожирая, стояли шпалеры бессониц в горячечном гаме рубанков;
б) По-прежнему, схлынувши с лиц очевидцев, безумствует быль, притворяясь незнающей;
в) ...впивая впотьмах это благо, бежала на чашечку с чашечки грозой одуренная влага-,
г) Я креплюсь на пере у творца крупной каплей густого свинца.
Для построенных систем вычислить значения уЛ, уП, ф. Указать для них «естественные» иерархизации.
ГП. 17. Построить «естественные» деревья подчинения для предложений из упражнения П1. 16. Проверить эти дервья на связанность с построенными при выполнении упражнения ГП. 16 иерархизован-НЫМИ системами состзеляющвд.
УПРАЖНЕНИЯ
313
Ш. 18. Иерархизовать каким-либо способом каждую из систем составляющих (1), (2) (стр. 283). Построить связанные с полученными иерархизациями деревья подчинения.
Ш. 19. Для каждого из деревьев подчинения рис. 15, а), б), в) построить все связанные с ним иерархизованные системы составляющих.
П1.20. Найти не менее 32 правильных анализов фразы: Назначение дежурным инструктором учителя Иванова вместо Петрова подтверждено Сидоренко.
Каким из этих анализов отвечают различные деревья подчинения и каким — одинаковые? Показать, что с помощью размеченных деревьев подчинения могут быть различены все 32 анализа.
ПРИЛОЖЕНИЕ II
ЗАМЕЩАЕМОСТЬ
Наряду с формальными грамматиками, представляющими собой «собственно модели языка», или, по терминологии Г. С. Цейтина [Цейтин 1959], «синтезирующие модели», существуют так называемые «анализирующие модели языка», или «модели лингвистического исследования». В синтезирующих моделях задаются некоторые сведения о строении механизма языка (например, в виде правил преобразования), и работа модели состоит в выполнении преобразований языковых выражений или порождении некоторых «текстов». В анализирующих моделях, напротив, считаются заданными некоторые совокупности «текстов», и задача состоит в извлечении из них той или иной информации о строении языка; таким образом, мы можем говорить в этом случае о «моделировании деятельности лингвиста». (Подробнее см. [Гладкий — Мельчук 1969, стр. 162—164].) Наиболее разработанный класс анализирующих моделей составляют те, которые основаны на понятии замещае-мости цепочек; им и посвящено настоящее приложение.
Предварительно необходимо сделать следующее замечание. При лингвистической интерпретации анализирующих моделей уже не безразлично, что понимать под элементарными символами — сегменты или словоформы (ср. введение, стр. 15—16). При втором понимании'в число исходных данных включаются грамматические значения, т. е. считаются заранее заданными такие понятия, как часть речи, падеж, род и т. п. Но это обесценивает модель — ведь именно построение формальных аналогов подобных понятий является ее целью, исходные же данные должны быть логически более простыми.
