Гладкий - Формальные грамматики и языки - 1973 (947381)
Текст из файла
613 Г 62 УДК 519-95 Формальные грамматики и языки. Гладкий А.В. Книга посвящена теории формальных грамматик и языков, являющейся важнейшей составной частью 'так называемой математической лингвистики. Эта теория вызвана к жизни потребностями лингвистики, но нашла сво)о почву в чистой математике и стала полноправной отраслью математической логики, тесно связанной с тео. рией алгоритмов и теорией автоматов. В книге рассматривается ряд важных проблем теории формальных грамматнк — таких, как взаимоотношения между различными классами грамматик п классами задаваемых ими языков, связь между грамматиками и автоматами, оценки сложностп вывода в грамматиках, алгоритмические проблемы для грамматик.
Книга представляет большой интерес для специалистов как в области математической лингвистики, так и в смежных областях, например в теории алгоритмов и автоматов. Страниц 368. Иллюстраций !7. Ллексей Всееолодоеыч Гладкой ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ М„1979 г., Збз стр.
с ллл. Редактор В. В. Волченко Техн. редактор В. Б. Взмокал Корректор Н, Б, Ркмлккзео Слзоо з езоар ю)н11 )972 г.подписано к оечзтк з)н шуз г, пумегз 9)х)99)о. тко. Ль2. Фкз. оеч, л. )1,9. услоек. оеч. л. 19,92. уч -кзд. л, 29,29, Тквзж 7999 зкз'. 7.99799, Иекз кклгк ) р. 9)'к. Ззкзз № 279 Издзтельстзо чНзукзь Глззкзе редакция флзкко.мзтемзткческой лктерзтуры 117071, Москва, В-7), Леккксккй проспект, !3 Ордекз Трудового Красного Зкзмекк Лекеосрздскз» ткоогрзфнфз № 2 ямекк Еегекек Соколовой ° Совзоологрзфоромз» орн Госудзрстоелком «омктете Созетз Мнккстроз СССР по делам яздзтельстз колкгрзфкл к книжной торгоелв г.
Ленинград, Л.З2, 1чзмзйлозсккй кросоект, 29 Г 0223-1714 942 (02)-73 О ГЛАБЛ ЕН И Е Предисловие 5 Введение ' 9 Г л а в а 1. Основные понятия ............. 17 й 1.0. Некоторые предварительные пояснения,..., . 17 й 1:1. Цепочки и языки....,...,...., 19 $1:2. Грамматики......,........ 25 9 !.3. Примеры грамматик............. 33 $1.4. Машины Тьюринга.............. 39. Упражнения .................. 50 Глава 2. Сигнализирующие функции.....,.... 55 $2.1. Сигнализирующие функции грамматик...... 55 $2:2. Сигнализирующие функции машин Тьюринга..., 62 $2.3.
Ускорение и сжатие выводов. Связь между сигнализирующими грамматик и машин......... 84 $2,4. Существование сколь угодно сложных рекурсивных язь)ков ............,..... 71 Упражнения .................. 75 Глава 3. Грамматики составляющих.......... 79 9 3.1. Деревья выводов.............. 79 $3.2. Неукарачивающие грамматики и машины Тьюринга без растяжения............... 34 $ 3.3. Сложность вывода в неукорачивающих грамматиках и НС.грамматиках .............. 89 9 3:4. Оценка временнбй сложности некоторых НС-языков .
93 9 3.5. 'НС-грамматики с односторонним контекстом..., 195 Упран)ненив , Ц1. Г л а в а 4. Бесконтекстные грамматики и машины с магазинной памятью . 1!5 $4.1. Некоторые вспомогательные утверждения . . . . . 115 $4.2. Распознавание пустоты и конечности Б-языка, Проекции ',',',',' .' ..' .'....,..., .', 12! 6 4 3. Необходимые условия бесконтекстности . . . . . . 128 Ф 4.4. Неоднозначность . . . . .
. . . . . . . . . 134' 9 4.5. Машяны с магазинной памятью...,..... 137' Упражнения 152' 1 ° ОГЛАВЛЕНИЕ Глава 5. Некоторые специальные классы бесконтекстных языков , 157 $5сй Автоматные и обобщенные автоматные языки. Конечные автоматы . . . . . . . . . . . . , . . !57 $ 5.2. Операции над ОА-языками. Регулярные языки . .
. 162 6 5.3. Лиаейные, металинейные и итерационно.линейные языки . . . . . . . . . . . . . . . . , . 168 й 5.4. Грамматики с ограниченной активной емкостью выво. дов. ОАЕВ-языки . . . . . . . . . . . . . . !74 Упражнения ......,.....,,.... 179 Глава 6. Дополнительные сведения о бесковтекстных грамма- тиках. Другие способы задания бесконтекстных языков . . .
, . . . , . . . . . . . . . , . 185 й 6.!. Категориальиые грамматики . . . . . . . . . . 185 $6.2. Нормальная форма Б-грамматики . . . . . . . . 196 6 6.3. Доминационяые грамматики......., .. 200 й 6.4. Системы уравнений в языках. Формальные степенные ряды . 207 3 6.5. Каноническое представление Б-языка . . . . . . 213 Упражнения ............... 218 Глава 7. Сложность вывода в бесконтекстных грамматиках . 221 й 7.1. Глубина н разброс . 221 6 7.2, Активная емкость . . . .
. . . , , . . . . , 228 6 7Б. Степень гнездования и степень самовставления . . 242 Упражнения .................. 249 Глава 8. Неразрешимые алгоритмические проблемы.... 252 й 8.1. Предварительные замечания........., 252 8.2. Инвариаитные свойства произвольных грамматик .. 256 8.3. Ипвариантные свойства НС-грамматик..... 260 6 8.4.
Некоторые проблемы, связанные с Б-грамматиками . 268 Упражнения . 279 Приложение 1. Системы составляющих и деревья синтаксического подчинения . . . . . . . . . 282 6 П1.1. Системы составляющих.....,..... 282 й П1.2. Деревья подчинения . . . . . . . . . . , . 294 6 П1. 3. Связь между системами составляющих и деревьями подчинения...,..., .. 304 Упражнения ...............
310 Приложен не П. Замещаемасть ........... 314 й ПП.1. Свободные полугруппы.... ',...., . 3!5 й ПП. 2. Замещаемость и взаимозамещаемость. Конфигурации,..., .' .'......... 3!8 й ПП.З. Окрестности, классы и типы....,.... 324 Упражнения .......... 340 Библиографические замечании..., ° °....., . 343 Литература,............ 349 Предметный указатель , , . . . . . , . . . . 357 Указатель обозначений .
. . . . . . 367 ПРЕДИСЛОВИЕ Настоящая книга представляет собой руководство по теории формальных грамматик, предназначенное для тех, кто хочет познакомиться с ее современным состоянием достаточно основательно — в общеобразователь- ных целях или ради прикладных задач (например, свя- ванных с языками программирования). Это первая книга такого рода на русском языке; монография (О)пзЬпгд 1966) е), русский перевод которой вышел в !970 г., посвящена исключительно бескоитекстным языкам **); другая недавно переведенная книга (Огозз — Ьеп1[п 1967) значительно элементарнее и содержит лишь основные понятия теории формальных грамматике**). Книга адресована в первую очередь читателю-математику; во всяком случае, для ее чтения нужна'извест- ') Фамилия и год в квадратвых скобках — ссылка на помещенный в канде книги список литературы.
Если в списке указано не. сколько работ одного автора, имеющих один и тот же год издания, то добавляются буквы в круглых скобках, например [СЬошзку 1959[б)1. "*) Кроме тато, в настоящей книге изложены некоторые разделы теории бесконтекстных языков, которых нет в [СипэЬпгк 19661: оценки сложности вывода, категориальные и доминациоиные грамматики, металинейные и итерационно-лннейные языки; подробнее трактуются алгоритмические проблемы.
С другой стороны, мы не рассматриваем преобразователей и ограниченных бесконтекстных языков, изучению которых уделено много внимания в кинге С. Гинзбурга. Еще одно отличие нашей книги от названной — мевьшая формализозанность изложения. "") Кроме названных двух, в мировой литературе имеется (на. сколько известно автору] еще только одна книга по формальным языкам [Норсгон — 1)!)шап 19691, также довольно сильно отлича|о1цаяся по содержанию от нашей.
прадисловие ная привычка к математическому мышлению и изучению математической литературы, Что касается фактических знаний, то формально их почти не требуется: достаточно владеть основными понятиями теории множеств. Тем не менее весьма желательно предварительное знакомство хотя бы с главными идеями и концепциями теории алгоритмов, в частности с машинами Тьюринга, поскольку «алгорнтмический дух» пронизынает всю теорию грамматик; не приобщившись к нему, невозможно составить представление о месте формальных грамматик в математике. При этом речь идет именно о направляющих идеях и общем духе: все относящиеся к алгоритмам технические определения — в терминах машин Тьюринга — в книге приводятся, и все необходимые факты доказываются *).
Лингвистические интерпретации упоминаются в основном тексте книги лишь изредка и вскользь (больше' внимания им уделено в приложениях 1 и П, но рассматриваемый там материал не относится, строга говоря, к грамматикам). Однако знакомство с лингвистическим' аспектом теории грамматик представляется автору полезным для ее изучения даже в чисто математическом плане; для ознакомления с этим аспектом можно рекомендовать книгу ~Гладкий — Мельчук 1969].
«Программистских» приложений мы не касаемся. В конце каждой главы помещены упражнения. Не- ' которые из них носят чисто тренировочный характер, но большинство предназначено служить дополнением к основному тексту; в упражнения вынесены многие факты, наличие которых в тексте не обязательно для логической последовательности изложения, а в отдельных случаях и такие утверждения, которые в дальнейшем ис- ") В частности, полностью замкнутым в себе сделано изложение нервврешимых алгоритмических проблем (гл. 8). Иэ теории влгоритмов в этом изложении используется только теорема Рейсе, докаввтельство которой приводится твм же.
првдисловив пользуются, если их доказательства просты и основаны на уже «отработанной» технике. Диапазон трудности упражнений весьма широк; к некоторым из наиболее трудных и наиболее важных даны краткие указания. Список литературы не претендует ни на какое подобие полноты; в него включены только те работы, которые упоминаются в книге, главным образом в библиографических замечаниях, также не претендующих на полный охват относящихся к делу источников.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
