Учебник. - Москва: Издательство Наука, 1973. - 368 с.
Книга посвящена теории формальных грамматик и языков, являющейся
важнейшей составной частью так называемой математической
лингвистики. Эта теория вызвана к жизни потребностями лингвистики,
но нашла свою почву в чистой математике и стала полноправной
отраслью математической логики, тесно связанной с теорией
алгоритмов и теорией автоматов. В книге рассматривается ряд важных
проблем теории формальных грамматик — таких, как взаимоотношения
между различными классами грамматик и классами задаваемых ими
языков, связь между грамматиками и автоматами, оценки сложности
вывода в рамматиках, алгоритмические проблемы для грамматик. Книга
представляет большой интерес для специалистов как в области
математической лингвистики, так и в смежных областях, например в
теории алгоритмов и автоматов.
Содержание:
Основные понятия
Сигнализирующие функции
Грамматики составляющих
Бесконтекстные грамматики и машины с магазинной
памятью
Некоторые специальные классы бесконтекстных языков
Дополнительные сведения о бесконтекстных грамматиках. Другие способы задания бесконтекстных языков
Сложность вывода в бесконтекстных грамматиках
Неразрешимые алгоритмические проблемы
Приложение I. Системы составляющих и деревья синтаксического подчинения
Приложение II. Замещаемость
Основные понятия
Сигнализирующие функции
Грамматики составляющих
Бесконтекстные грамматики и машины с магазинной
памятью
Некоторые специальные классы бесконтекстных языков
Дополнительные сведения о бесконтекстных грамматиках. Другие способы задания бесконтекстных языков
Сложность вывода в бесконтекстных грамматиках
Неразрешимые алгоритмические проблемы
Приложение I. Системы составляющих и деревья синтаксического подчинения
Приложение II. Замещаемость