Издательство «Наука», главная редакция физико-математической литературы, Москва, 1973. – 368 стр.
Книга посвящена теории формальных грамматик и языков, являющейся важнейшей составной частью так называемой математической лингвистики. Эта теория вызвана к жизни потребностями лингвистики, но нашла свою почву в чистой математике и стала полноправной отраслью математической логики, тесно связанной с теорией алгоритмов и теорией автоматов. В книге рассматривается ряд важных проблем теории формальных грамматик — таких, как взаимоотношения между различными классами грамматик и классами задаваемых ими языков, связь между грамматиками и автоматами, оценки сложности вывода в грамматиках, алгоритмические проблемы для грамматик. Книга представляет большой интерес для специалистов как в области математической лингвистики, так и в смежных областях, например в теории алгоритмов и автоматов.
 А. В. Гладкий. Формальные грамматики и языки | [ ] | 12219 Kb |
ОГЛАВЛЕНИЕ
Предисловие [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]