Theory of formal languages for text and communication

2023/2024

Academic Year

RUS

Instruction in Russian

6

ECTS credits

Delivered at:

School of Linguistics

Course type:

Compulsory course

When:

1 year, 2, 3 module

Instructor

Klyshinskiy, Eduard

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

Аннотация

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

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

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

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

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

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

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

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

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

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

• 2023/2024 учебный год 3 модуль
  0.6 * Итоговый проект + 0.2 * Лабораторные работы + 0.2 * Лабораторные работы

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

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

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

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

• Каширская, Е. Н. Теория конечных автоматов : учебное пособие / Е. Н. Каширская, М. М. Клягин, В. А. Серебрянкин. — Москва : РТУ МИРЭА, 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