Основная профессиональная образовательная программа высшего образования

Содержание основных разделов (тем) курса

1. 
   Формальные языки. Контекстно-свободные грамматики.
   

Алфавиты и языки. Формальное определение грамматики. Типы грамматик. Деревья вывода в контекстно-свободных грамматиках.

2. 
   Регулярные языки. Регулярные выражения
   

Операторы регулярных выражений. Построение регулярных выражений. применение регулярных выражений. Регулярные языки.

3. 
   Конечные автоматы.
   

Формальное определение конечного автомата. Недетерминированные конечные автоматы. Конечные автоматы и языки типа 3. Конечные автоматы и регулярные выражения.

4. 
   Магазинные автоматы.
   

Формальное определение магазинного автомата. Представление контекстно-свободных языков магазинными автоматами

5. 
   Контекстно-зависимые грамматики
   

Иерархия грамматик по Хомскому. Контекстно-зависимые грамматики. Грамматики Ван Вайнгаардена.

6. 
   Машины Тьюринга.
   

Основные понятия и принципы действия. Примеры машин Тьюринга для принятия перечислимого языка и для вычисления функции. Модификации машин Тьюринга. Односторонние и многоленточные машины. Недетерминированные машины Тьюринга.
Тематика практических занятий

1. 
   Формальные языки. Контекстно-свободные грамматики.
   
2. 
   Регулярные языки. Регулярные выражения.
   
3. 
   Детерминированные и недетерминированные конечные автоматы.
   
4. 
   Конечные автоматы и регулярные выражения.
   
5. 
   Магазинные автоматы.
   
6. 
   Контекстно-зависимые грамматики.
   
7. 
   Машины Тьюринга
   
8. 
   Построение машин Тьюринга для принятия перечислимого языка и для вычисления функции
   
9. 
   Недетерминированные машины Тьюринга.
   

Трудоёмкость (з.е. / часы)	Согласно рабочему учебному плану курс читается в полном объёме в течение 6 семестра 3 ЗЕТ / 108 часов.
Форма итогового контроля знаний	В конце 6-го семестра предусмотрен зачет.

Аннотация учебной дисциплины

Учебная дисциплина «ФУНКЦИОНАЛЬНЫЕ ПОЛЯ И ИХ ПРИЛОЖЕНИЯ»
Цель изучения дисциплины