Вид документа : Однотомное издание Шифр издания : 97548 Автор(ы) : Пентус А. Е., Пентус М. Р. Заглавие : Математическая теория формальных языков : Учебное пособие Выходные данные : Москва: Интернет-Университет Информационных Технологий (ИНТУИТ), Ай Пи Ар Медиа, 2020 Колич.характеристики :218 с Примечания : Книга находится в Премиум-версии ЭБС IPRbooks. ISBN, Цена 978-5-4497-0662-1: Б.ц. УДК : 519 ББК : 22.1 Ключевые слова (''Своб.индексиров.''): автоматный язык--иерархия хомского--конечный автомат--контекстно-свободная грамматика--магазинная память--математическая теория--машина тьюринга--теоретическая информатика--формальный язык Аннотация: Учебное пособие посвящено классическому разделу математической лингвистики и теоретической информатики — теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью. Затронуты следующие классические темы математических основ информатики: праволинейные грамматики, конечные автоматы, регулярные выражения, контекстно-свободные грамматики, деревья разбора, нормальные формы грамматик, автоматы с магазинной памятью, детерминированные контекстно-свободные языки, синтаксический анализ, контекстные грамматики, линейно ограниченные автоматы, порождающие грамматики без ограничений, машины Тьюринга, алгоритмические проблемы, связанные с грамматиками и автоматами. Особое внимание уделено практическим способам выяснения, к какому классу в иерархии Хомского принадлежит заданный язык, методам преобразования регулярных выражений и автоматов в грамматики соответствующего класса и наоборот, а также доказательству неразрешимости проблем, связанных с контекстно-свободными грамматиками. Доп.точки доступа: Пентус, М. Р.