Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Формальные языки и автоматы
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Системное программирование и компьютерные науки
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299) 

1. Дисциплина относится к вариативной части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по алгоритмам и алгоритмическим языкам, системам программирования, дискретной математике в объеме, соответствующем программе первых двух лет обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
•	ОПК-2.Б Способность применять и модифицировать математические модели, а также интерпретировать полученные математические результаты при решения задач в области профессиональной деятельности 
•	ПК-2.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат
•	ПК-4.Б Способность применять в профессиональной деятельности современные средства разработки программного обеспечения и методы параллельной обработки данных, реализовывать отдельные этапы разработки системного и прикладного программного обеспечения, систем обработки и анализа данных, сетевых технологий

Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	основы теории формальных языков;
2.	основы теории автоматов;
3.	основы методов трансляции.

Уметь:
1.	строить регулярное выражение для заданного формального языка;
2.	строить конечные автоматы для распознавания заданного формального языка;
3.	анализировать свойства формальных языков;
4.	строить автомат с магазинной памятью и другие анализаторы для распознавания заданного контекстно-свободного языка;

Владеть:
1.	навыками разработки трансляторов с языков программирования.

4. Формат обучения: лекции проводятся при помощи компьютера и мультимедийного проектора, семинарские занятия проводятся с использованием меловой доски.

5. Объем дисциплины (модуля) составляет 4 з.е., в том числе 48 академических часа, отведенных на контактную работу обучающихся с преподавателем, 96 академических часов на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий.
Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Формальные языки и их представление	10	4	2	6	4	
2.	Классификация языков по Хомскому	10	4	2	6	4	
3.	Регулярные языки и конечные автоматы	10	4	2	6	4	
4.	Текущий контроль успеваемости: контрольная работа №1. 	2	0	0	0	2	
5.	Текущий контроль успеваемости: практическое задание №1	12	0	0	0	12	
6.	Контекстно-свободные языки и магазинные автоматы	20	8	4	12	8	
7.	Синтаксический анализ сверху-вниз	15	6	3	9	6	
8.	Синтаксический анализ снизу-вверх  	15	6	3	9	6	
9.	Текущий контроль успеваемости: контрольная работа № 2	2	0	0	0	2	
10.	Текущий контроль успеваемости: практическое задание №2	12	0	0	0	12	
Промежуточная аттестация: письменный экзамен	36	0	0	0	36	
Итого	144	32	16	48	96	
7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.

Типы заданий контрольной работы №1
1.	Построить РВ, описывающее заданный язык.
2.	Построить НКА по РВ.
3.	Построить ДКА по РВ.
4.	Построить минимальный ДКА, эквивалентный данному ДКА.
5.	Построить ДКА для симметрической разности двух языков, заданных ДКА.
6.	Построить ДКА, принимающий заданный язык.
7.	С помощью леммы о накачке доказать, что заданный язык не является регулярным.

Типы заданий контрольной работы №2
1.	Привести грамматику к нормальной форме Хомского.
2.	Построить МП-автомат для заданного языка.
3.	Построить -анализатор для языка, заданного КС-грамматикой.
4.	При помощи алгоритма Кока-Янгера-Касами определить, принадлежит ли цепочка заданному КС-языку.
5.	Доказать, что заданный язык не является КС.
6.	Построить -анализатор для языка, заданного КС-грамматикой.

Письменные опросы

Во время лекций проводятся письменные опросы. Каждый опрос включает 3 тестовых вопроса, подобранных случайным образом из множества заготовленных заданий для обеспечения индивидуальных вариантов. Пример варианта опроса:
1.	На обратной стороне нарисуйте диаграмму ДКА, распознающего целые десятичные числа больше 1. (Можно использовать запись ``5..9'' для сокращения количества стрелок)
2.	Напишите регулярное выражение, задающее множество цепочек из нулей и единиц, содержащих не более одной пары последовательных единиц.
3.	Приведите примеры таких языков L_1, L_2, что L_1 \subseteq L_2 и L_1 -- регулярный, а L_2 -- нерегулярный. Будьте готовы доказать регулярность/нерегулярность L_1 и L_2.

Практические задания

1.	Построить лексический анализатор для модельного языка при помощи генератора лексических анализаторов LEX. Подготовить репрезентативный набор тестовых данных для поверки корректности результатов и обработки ошибок во входных данных. Пройти автоматизированную проверку разработанного ПО в системе ejudge.
2.	Построить синтаксический анализатор с использованием лексического анализатора, разработанного в практическом задании №1. Реализовать транслятор с модельного языка в промежуточное представление вида 3-адресный код. Подготовить репрезентативный набор тестовых данных для поверки корректности результатов и обработки ошибок во входных данных. Пройти автоматизированную проверку разработанного ПО в системе ejudge.

7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

Программа экзамена по курсу
1.	Грамматики (определение грамматики, классификация и примеры)
2.	Регулярные множества и выражения, конечные автоматы (РМ, РВ, КА).
3.	Построение ДКА по НКА. Алгоритм построения КА по РВ.
4.	Связь РМ, КА и регулярных грамматик. 
5.	Автоматы с МП (определения и примеры). Связь МП-автоматов и КС-грамматик. Приведённые грамматики (алгоритмы)
6.	Лемма о разрастании (применение при доказательстве не-КС-грамматик).
7.	Функции FIRST и FOLLOW.  LL(k) –грамматики (определения и примеры).
8.	Необходимые и достаточные условия. Построение LL(1)-анализатора.
9.	LR(k)-грамматики (определения и примеры).
10.	LR(k)-анализатор. 
11.	Необходимые и достаточные условия LR(k). 

Вариант письменного экзамена по курсу

1.	Напишите регулярное выражение, задающее множество всех цепочек в алфавите , которые содержат не более трёх символов  подряд.
2.	Для заданной КС-грамматики  постройте эквивалентную -грамматику. Докажите, что получившаяся грамматика является -грамматикой.
.
3.	Постройте ДКА по РВ .
4.	Над алфавитом  задан язык . Докажите, что язык  не является контекстно-свободным.
5.	Постройте -анализатор для грамматики , где 

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Экзамен	Отсутствие знаний	Фрагментарные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Практические задания №№1 и 2
Контрольные работы №№1 и 2	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципи-ального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	основы методов трансляции.	
ОПК-1.Б	
Знать:
1.	основы теории формальных языков;
2.	основы теории автоматов;	

ОПК-2.Б	
Знать:
1.	основы методов трансляции.
Уметь:
1.	строить регулярное выражение для заданного формального языка;
2.	строить конечные автоматы для распознавания заданного формального языка;
3.	анализировать свойства формальных языков;
4.	строить автомат с магазинной памятью и другие анализаторы для распознавания заданного контекстно-свободного языка;
Владеть:
1.	навыками разработки трансляторов с языков программирования.
	
ПК-2.Б	
Владеть:
1.	навыками разработки трансляторов с языков программирования.	
ПК-4.Б	

8. Ресурсное обеспечение:

Основная литература:
  
1.	А.Ахо, Д.Ульман.
Теория синтаксического анализа, перевода и компиляции. Т. 1,2.
Мир, 1978. 
2.	Д.Хопкрофт, Р.Мотвани, Д.Ульман.
Введение в теорию автоматов, языков и вычислений.
Вильямс, 2002.
3.	А.Ахо, Р.Сети, Д. Ульман.
Компиляторы: принципы, технологии, инструменты.
Вильямс, 2003.
4.	Серебряков В.А.
Теория и реализация языков программирования. 
Физматлит, 2012.
5.	K.Cooper, L.Torczon
Engineering a compiler
Morgan Kaufmann; 2nd edition (February 21, 2011)

Информационные справочные системы:

http://flcourse.cs.msu.su – страница курса. Слайды лекций доступны на https://getbox.ispras.ru/index.php/s/z1xnZhUNOd2E0OU

Материально-техническое обеспечение:  Используются традиционные технологии проведения лекций с показом слайдов. Учебные и методические материалы опубликованы на странице курса. По этому адресу также осуществляется информирование студентов о текущих событиях курса, результатах коллоквиумов и т. п. Для сдачи практических заданий используется система автоматической проверки ejudge.

9. Язык преподавания - русский.

10. Преподаватели:  	профессор факультета ВМК МГУ Серебряков В.А., к.ф.-м.н. Игнатьев В.Н., Теймуразов К.Б., Батузов К.А.

11. Авторы программы:  профессор факультета ВМК МГУ Серебряков В.А., к.ф.-м.н. Игнатьев В.Н.