Формальные грамматики и языки
Автор(ы): | Гладкий А. В.
28.04.2015
|
Год изд.: | 1973 |
Описание: | Книга посвящена теории формальных грамматик и языков, являющейся важнейшей составной частью так называемой математической лингвистики. Эта теория вызвана к жизни потребностями лингвистики, но нашла свою почву в чистой математике и стала полноправной отраслью математической логики, тесно связанной с теорией алгоритмов и теорией автоматов. В книге рассматривается ряд важных проблем теории формальных грамматик — таких, как взаимоотношения между различными классами грамматик и классами задаваемых ими языков, связь между грамматиками и автоматами, оценки сложности вывода в грамматиках, алгоритмические проблемы для грамматик. Книга представляет большой интерес для специалистов как в области математической лингвистики, так и в смежных областях, например в теории алгоритмов и автоматов. |
Оглавление: |
Обложка книги.
Предисловие [8]Введение [9] Глава 1. Основные понятия [17] § 1.0. Некоторые предварительные пояснения [17] § 1:1. Цепочки и языки [19] § 1:2. Грамматики [25] § 1:3. Примеры грамматик [33] § 1.4. Машины Тьюринга [39] Упражнения [50] Глава 2. Сигнализирующие функции [55] § 2.1. Сигнализирующие функции грамматик [55] § 2.2. Сигнализирующие функции машин Тьюринга [62] § 2.3. Ускорение и сжатие выводов. Связь между сигнализирующими грамматик и машин [64] § 2.4. Существование сколь угодно сложных рекурсивных языков [71] Упражнения [75] Глава 3. Грамматики составляющих [79] § 3.1. Деревья выводов [79] § 3.2. Неукорачивающие грамматики и машины Тьюринга без растяжения [84] § 3.3. Сложность вывода в неукорачивающих грамматиках и НС-грамматиках [89] § 3.4. Оценка временной сложности некоторых НС-языков [93] § 3.5. НС-грамматики с односторонним контекстом [105] Упражнения [111] Глава 4. Бесконтекстные грамматики и машины с магазинной памятью [115] § 4.1. Некоторые вспомогательные утверждения [115] § 4.2. Распознавание пустоты и конечности Б-языка. Проекции [121] § 4.3. Необходимые условия бесконтекстности [126] § 4.4. Неоднозначность [134] § 4.5. Машины с магазинной памятью [137] Упражнения [152] Глава 5. Некоторые специальные классы бесконтекстных языков [157] § 5.1. Автоматные и обобщенные автоматные языки. Конечные автоматы [157] § 5.2. Операции над ОА-языками. Регулярные языки [162] § 5.3. Линейные, металинейные и итерационно-линейные языки [168] § 5.4. Грамматики с ограниченной активной емкостью выводов. ОАЕВ-языки [174] Упражнения [179] Глава 6. Дополнительные сведения о бесконтекстных грамматиках. Другие способы задания бесконтекстных языков [185] § 6.1. Категориальные грамматики [185] § 6.2. Нормальная форма Б-грамматики [196] § 6.3. Доминационные грамматики [200] § 6.4. Системы уравнений в языках. Формальные степенные ряды [207] § 6.5. Каноническое представление Б-языка [213] Упражнения [218] Глава 7. Сложность вывода в бесконтекстных грамматиках [221] § 7.1. Глубина и разброс [221] § 7.2. Активная емкость [228] § 7.3. Степень гнездования и степень самовставления [242] Упражнения [249] Глава 8. Неразрешимые алгоритмические проблемы [252] § 8.1. Предварительные замечания [252] § 8.2. Инвариантные свойства произвольных грамматик [256] § 8.3. Инвариантные свойства НС-грамматик [260] § 8.4. Некоторые проблемы, связанные с Б-грамматиками [268] Упражнения [279] Приложение I. Системы составляющих и деревья синтаксического подчинения [282] § ПI.1. Системы составляющих [282] § ПI.2. Деревья подчинения [294] § ПI.3. Связь между системами составляющих и деревьями подчинения [304] Упражнения [310] Приложение II. Замещаемость [314] § ПII.1. Свободные полугруппы [315] § ПII.2. Замещаемость и взаимозамещаемость. Конфигурации [318] § ПII.З. Окрестности, классы и типы [324] Упражнения [340] Библиографические замечания [343] Литература [349] Предметный указатель [357] Указатель обозначений [367] |
Формат: | djvu |
Размер: | 3930707 байт |
Язык: | РУС |
Рейтинг: | 152 |
Открыть: | Ссылка (RU) |