Экзаменационная программа по курсу «Теория автоматов и формальных языков», 2008/09 уч. год
Материал из Вики ИТ мехмата ЮФУ
Версия от 01:53, 8 июня 2009; Avalanche (обсуждение | вклад)
Экзаменационная программа по курсу «Теория автоматов и формальных языков»
2008/09 учебный год.
Факультет математики, механики и компьютерных наук.
Специальность: Информационные технологии. 2-ой курс, весна.
Лектор: Деундяк Владимир Михайлович.
- Полугруппы и моноиды. Степени. Свойства степеней. Подполугруппы иподмоноиды. Примеры.
- Алфавит. Слова. Операции над словами. Префиксы и суффиксы, подслова. Длина слова. Примеры.
- Язык над алфавитом Σ. Пустой язык. Язык Σ*. Язык Σ* как моноид. Операции над языками. Примеры.
- Грамматики. Выводимые слова. Язык, порождаемый грамматикой. Примеры.
- Общая схема автомата распознавателя.
- Классификация Хомского формальных языков. Примеры.
- Регулярные множества. Регулярные выражения. Примеры.
- Лемма о регулярных выражениях.
- Линейные уравнения с регулярными коэффициентами. Неподвижная точка. Теорема.
- Системы линейных уравнений с регулярными коэффициентами. Алгоритм Гаусса. Примеры.
- Лемма о праволинейности элементарных языков. Лемма о праволинейност результатов операций над ПЛ-языками. Следствие. Лемма о регулярности ПЛ-языков (схема доказательства).
- Конечные автоматы. Конфигурация. Достижимые состояния. Такт. Язык L(M), определяемый автоматом M. Примеры автоматов.
- Детерминированные и недетерминированные автоматы. Теорема о редукции (схема доказательства).
- Лемма о праволинейности конечных автоматов (схема доказательства).
- Лемма об автоматности элементарных языков (схема доказательства).
- Лемма об автоматности результатов операций над языками (схема доказательства).
- Теорема о совпадении праволинейных, регулярных и автоматных языков.
- Алгоритм 1 проверки КС-грамматики на непустоту. Алгоритм 2 построения по КС-грамматике стабилизационного множества. Примеры.
- Недостижимые и бесполезные символы в КС-грамматике. Алгоритм 3 устранения у КС-грамматик недостижимых символов. Алгоритм 4 устранения у КС-грамматик бесполезных символов. Примеры.
- Неукорачивающиеся КС-грамматики. Алгоритм 5 преобразования КС-грамматик к неукорачивающемуся виду. Примеры.
- Цепные продукции в КС-грамматиках. КС-грамматики без циклов. Алгоритм 6 удаления цепных продукций. Примеры.
- Приведенные КС-грамматики. Алгоритм преобразования КС-грамматик к приведенному виду. Примеры.
- МП-автоматы. Конфгурация. Достижимые состояния. Такт. Язык L(M), определяемый МП-автоматом M. Примеры. ДМП-автоматы.
- Нормальная форма Хомского КС-грамматик. Алгоритм преобразования КС-грамматик к нормальной форме Хомского. Примеры.
- Каноническая форма Грейбах КС-грамматик. Примеры.
- РМП-автоматы. Языки L(M) и Lm(M), определяемые РМП-автоматом M. Теорема о совпадении языков.