Формальные грамматики и языки

Автор(ы):Гладкий А. В.
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)