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

Цели и задачи дисциплины

Дисциплина «Теория автоматов и формальных языков» обеспечивает приобретение знаний и умений в соответствии с государственным образовательным стандартом, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Теория автоматов и формальных языков» является подготовка специалистов к деятельности в сфере разработки, исследования и эксплуатации информационных систем.

Краткое содержание дисциплины

Введение. Конечные автоматы. Свойства автоматных языков. Регулярные выражения. Минимизация детерминированных конечных автоматов. Контекстно-свободные (КС) грамматики и языки. Свойства КС-языков. Автоматы с магазинной памятью.

Компетенции обучающегося, формируемые в результате освоения дисциплины

Выпускник должен обладать:

ОПК-1 Способен применять фундаментальные знания, полученные в области математических и (или) естественных наук, и использовать их в профессиональной деятельности

В результате освоения дисциплины студент должен знать

классификацию грамматик в соответствии с иерархией Хомского основные алгоритмически разрешимые и неразрешимые проблемы теории автоматов и формальных языков

В результате освоения дисциплины студент должен уметь

задавать язык с помощью грамматики и регулярного выражения, а также строить конечные автоматы требуемого вида (детерминированные, полные, минимальные) для распознавания различных языков (ПК-1, ПК-3);

В результате освоения дисциплины студент должен владеть

— освоить алгоритмы построения конечного автомата по праволинейной грамматике и наоборот, автомата с магазинной памятью по контекстно-свободной грамматике и наоборот — научиться определять, являются ли автоматными данные словарные функции и языки;