Теория формальных языков для текста и коммуникации

2024/2025

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

Школа лингвистики

Статус:

Курс обязательный

Когда читается:

1-й курс, 3, 4 модуль

Преподаватель

Клышинский Эдуард Станиславович

Программа дисциплины

Аннотация

Данный курс посвящен изучению основ теории формальных языков применительно к анализу текстов на естественном языке. В рамках курса изучается теория построения конечных автоматов, написания грамматик в формах Бэкуса-Науэра, обработки контекстно-свободных грамматик. В рамках курса мы получим опыт написания грамматик для разработки простых фрагментов текста, выделения его элементов.

Цель освоения дисциплины

• Целью освоения дисциплины является ознакомление студентов с методами разбора текстов с использованием теории формальных языков. Курс необходим для понимания процессов, протекающих в современных системах анализа текстов.

Планируемые результаты обучения

• строить и анализировать конечные автоматы
• Контекстно-свободные языки. Формальные грамматики и магазинные автоматы. Алгоритм построения МП-автомата по грамматике.
• Знать формальное определение языка при помощи грамматики, представление грамматики в виде БНФ.
• Уметь применять конечные автоматы для анализа цепочек.
• Знать определение LR(k)-грамматики. Знать метод разбора с использованием стека и управляющего устройства.
• Нормальная форма Хомского. Алгоритм Кока–Янгера–Касами. Лемма о накачке для КС-языков.

Содержание учебной дисциплины

• Теория формальных языков
• Конечные автоматы
• МП-автоматы, LR(1)-грамматики и их разбор
• Синтаксический анализ текстов на естественном языке при помощи формальных грамматик

Элементы контроля

• Лабораторные работы
• Итоговый проект

Промежуточная аттестация

• 2024/2025 4th module
  0.6 * Итоговый проект + 0.2 * Лабораторные работы + 0.2 * Лабораторные работы

Список литературы

Рекомендуемая основная литература

• Алымова, Е. В. Конечные автоматы и формальные языки : учебник / Е. В. Алымова. В. М. Деундяк. А. М. Пеленнцын ; Южный федеральный университет. - Ростов-на-Дону : Таганрог : Издательство Южного федерального университета. 2018. - 292 с. - ISBN 978-5-9275-2397-9. - Текст : электронный. - URL: https://znanium.com/catalog/product/1020503
• Малявко, А. А.  Формальные языки и компиляторы : учебное пособие для вузов / А. А. Малявко. — Москва : Издательство Юрайт, 2022. — 429 с. — (Высшее образование). — ISBN 978-5-534-04288-7. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/492129 (дата обращения: 27.08.2024).

Рекомендуемая дополнительная литература

• Каширская, Е. Н. Теория конечных автоматов : учебное пособие / Е. Н. Каширская, М. М. Клягин, В. А. Серебрянкин. — Москва : РТУ МИРЭА, 2021. — 100 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/226538 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Компиляторы : краткий справочник: пер. с англ., Хантер, Р., 2018
• Компиляторы: принципы, технологии и инструменты, Ахо, А. В., 2011
• Руднева, Л. Ю. Теория конечных автоматов. Практикум : учебное пособие / Л. Ю. Руднева, И. Ю. Зайцев, М. М. Клягин. — Москва : РТУ МИРЭА, 2022. — 96 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/265667 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Унгер, А. Ю. Теория формальных языков : учебное пособие / А. Ю. Унгер. — Москва : РТУ МИРЭА, 2022. — 77 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/239975 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Формальные языки и компиляторы : учебное пособие для вузов, Малявко, А. А., 2017

Авторы

• Клышинский Эдуард Станиславович