Гладкий - Формальные грамматики и языки - 1973 (947381), страница 62
Текст из файла (страница 62)
П1.2. йусть з, — число систем составляющих одноз цепочки длины л ~ 2 и з, (! ( ! ( л) — число тех из этих систем, для которых крайняя справа точка цепочки служит концом ! различных составляющих. Показать, что л а) за+~ ~Ч~~ (21 — !) ° злн ! 2 б) злвь! зл, г-~+2 ~~'~ зл1. П!.3. Доказать, что граф (С;=з=>) (стр. 287) является деревом. П1.4. Пусть Ь, — число бинарных систем составляющих одной цепочки длины л ~ 2.
а) Указать рекуррентную формулу, выражающую Ь ы через Ьь ..., Ь . б) Показать, что для каждой системы составляющих С цепочки к ((х( ) 2) существует точно П ьн > содержащих ее биАюо парных систем составляющих той же цепочки, где 1(А) — ширина куста составляющей А в системе С (Ьэ считается равным единице). П1.5. Пусть С вЂ” система составлнюших ранга г и ширины Обозначим через 1с число различных иерархизаций системы С и через 1г! — число 1 1г ° (д)! ° ... ° (... (У)г ...)~, где последний сомножитель содержит г — ! возведений в степень. Показать, чтщ а) если ширина куста каждой неточечной составляющей системы С равна 1, то 1 =1 д го б) в общем случае 1,я~(!с~1 !.
П1.8. Построить «естественное» дерево подчинения для формулы (5) (стр. 284). П1.7. Показать, что всякая небинарная система составляющих, согласованная с некоторым деревом подчинения, содержится в не. которой другой системе составляющих, согласованной с тем же деревом. Таким образом, в множестве всех систем составляющих, согласованных с данными деревом подчинения, система Сз (стр.
305) является наименьшим элементом (относительно теоретико-множественною включения), а бинарные системы — максимальными элементами. П1. 8. Показать, что согласованная с деревом (Х; -») система со. ставляющих тогда и только тогда единственна, когда (Х,-») — дерево без ветвления (т. е. каждая его вершина имеет не более одной подчиненной).
П1.9. Пусть Я вЂ” множество всех систем составляющих, согласованных с деревом (х;-»), и для сь сз щ 5 запись с~==,'ьсз означает, что С, с Сз и не существует системы С' щ Я такой, что С, с С' с С,. Показать, что длина любого максимального пути в графе (5; ю ь) (такой путь, вообще говоря, не один) равна сумме уменьшенных иа единицу ширин кустов невисячих узлов дерева (Х; -»), упражнения 813 312 СИСТЕМЫ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЯ ПОДЧИНЕНИЯ [П. 1 П[.10. Показать, что бинарная система составляющих, согласо- ванная с деревом (Х; -»), тогда и только тогда единственна, когда для каждого узла этого дерева все подчиненные ему узлы располо- жены по одну сторону от него.
П1.11. Показать, что высота дерева подчинения, согласованного с системой составляющих, не превосходит высоты этой системы. П[. 12. Показать, что система составляющих С и дерево подчине. ния (Х; -о) тогда и только тогда согласованы, когда: а) группы зависимости всех узлов дерева (Х;-») являются составллющими си. стемы С; б) каждая составляющая системы С совпадает с множе. ством узлов некоторого поддерева дерева (Х; -») . П[.13. Показать, что объединение множества подформул (в обычном смысле) произвольной формулы Р исчисления предикатоЪ, (как в «скобочной», так и в бесскобочной записи) с множеством вхо.
ждений в Р элементарных символов является системой составляю- щих для Р. П[.14. Назовем системы составляющих С и С, цепочек х и х, подобными, если изображающие их скобочные последователь- ности совпадают. а) Сформулировать определение подобия, не упоминая о скобоч- ных нли иных изображениях. б) Показать, что если Р— формула исчисления предикатов в «скобочной» записи н Р~ — та же формула в бесскобочной записи, то описанные в упражнении П1. 13 системы составляющих цепочек Р и Ро подобны. П!.15. Показать, что если дерево подчинения (Х; — ) связано ' с нерархизованной системой составляющих (С, С') цепочки х, а — ' точка цепочки х и Во =о В,:о... ~ Во — †(ы) — все составляющие, для которых и служит главной точкой (так что Во — группа зависи.
мости узла а), то ширина куста узла и в дереве (Хг-н) равна (!о — 1)+ ° . +(!о-~ — !), где' И вЂ” ширина куста составляющей Вь 3 а м е ч а н н е. Если з, — степень составляющей Во, то ' со! ~~ ([о — 1)+ ..+([~ 1 — 1), так что ширина куста а не ' может быть меньше зо. Поэтому степень системы С ие превосходит ' ширины дерева (Х; -»). П!. 16. Построить «естественные» системы составляющих для предложений: а) Века пожирая, стояли шпалеры бессониц в гарячесйом гаме рубакков; б) По-прежнему, охлынувши с лиц очевидцев, безумствует босха, притворяясь незнаюи[еи; в) ...впивая елатьма«это благо, бежала на чашечку с чашечки грозой одуренкая влага; г) Я креплюсь на пере у творца крупной каплей густого свинца. Для построенных систем вычислить значения у , уп, ф. Ука- зать для них <естественные» иерархизации. П!.
17. Построить «естественные» деревья подчиаения для пред- ' ложений из упражнения П[.16. Проверить эти дервья на связанность: с построенными при выполневии упражнения П[.16 иерархиэоваяиыми системами составлнющрк, П1.18. Иерархизовать каким. либо способом каждуоо из систем составляющих (1), (2) (стр. 283). Построить связанные с полученными иерархизациями деревья подчинения. П!. 19. Для каждого из деревьев подчинения рис.
15,а), б), в) построить все связанные с ннм иерархизованные системы составляющих. П[.20. Найти не менее 32 правильных анализов фразы: Назначение дежурным инструктором учителя Иванова вместо Петрова подтверждено Сидоренко. Каким из этих анализов отвечают различные деревья подчинения и каким — одинаковые? Показать,,что с помощью размеченных деревьев подчинения могут быть различеиы все 32 анализа. СВОБОДНЫЕ ПОЛУГРУППЫ 3!5 э пнз ПРИЛОЖЕНИЕ Н ЗАМЕЩАЕМОСТЪ Наряду с формальными грамматиками, представляю. щнми собой «собственно модели языка», или, по терминологии Г. С. Цейтина 1Цейтин 1959), «синтезирующие модели», существуют так называемые «анализирующие модели языка», или «модели лингвистического исследования». В синтезирующих моделях задаются некоторые сведения о строении механизма языка (например, в виде правил преобразования), и работа модели состоит в выполнении преобразований языковых выражений или порождении некоторых «текстов».
В анализирующих моделях, напротив, считаются заданными некоторые совокупности <текстов», и задача состоит в извлечении из них той или иной информации о строении языка; таким образом, мы можем говорить в этом случае о «моделировании деятельности лингвиста».
(Подробнее см. (Гладкий — Мельчук 1969, стр. 162 — 164).) Наиболее разработанный класс анализирующих моделей составляют те, которые основаны на понятии замещаемости цепочек; им и посвящено настоящее приложение. Предварительно необходимо сделать следующее замечание. При лингвистической интерпретации анализирующих моделей уже не безразлично, чтб понимать под элементарными символами — сегменты или словоформы (ср. введение, стр. 15 — 16). При втором понимании в число исходных данных включаются грамматические значения, т.
е. считаются заранее заданными такие понятия, как часть речи, падеж, род и т. п. Но это обесценивает модель — ведь именно построение формальных аналогов подобных понятий является ее целью, исходные же данные должны быть логически более простыми, С другой стороны, опираясь лишь на понятие сегмента, относящееся целиком к внешней стороне языка, можно рассчитывать получить лишь довольно «бедные» модели (ср. ниже, стр. 327). Поэтому представляется целесообразным включить в число исходных данных лексические значения слов.
Для этого мы введем понятие лексически значимого сегмента (ЛЗ-сегмента), промежуточное между понятиями сегмента и словоформы; именно, ЛЗ-сегмент — это сегмент, снабженный лексическм значением (но не грамматическими). Например, в предложении Он говорит только о физике, читает книги только но физике, и о нем говорят только как о физике первые два вхождения сегмента физике являются вхождениями одного и того же ЛЗ-сег. мента — но разных словоформ! — а третье отвечает дру.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
