Математическая теория формальных языков

Предварительный просмотр:

О книге:

Курс посвящён классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие
грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью. Затронуты следующие классические темы математических основ информатики:
праволинейные грамматики, конечные автоматы, регулярные выражения, контекстно- свободные грамматики, деревья разбора, нормальные формы грамматик, автоматы с
магазинной памятью, детерминированные контекстно-свободные языки, синтаксический анализ, контекстные грамматики, линейно ограниченные автоматы, порождающие грамматики без ограничений, машины Тьюринга, алгоритмические проблемы, связанные с грамматиками и автоматами. Особое внимание уделено практическим способам выяснения, к какому классу в иерархии Хомского принадлежит заданный язык, методам преобразования регулярных выражений и автоматов в грамматики соответствующего класса и наоборот, а также доказательству
неразрешимости проблем, связанных с контекстно-свободными грамматиками.