В.А. Кутыркин, А.Ю. Бушуев Элементы теории автоматов и формальных языков. (В.А. Кутыркин, А.Ю. - Бушуев Элементы теории автоматов и формальных языков. 2014)

Московский государственный технический университетимени Н.Э. БауманаФакультет «Фундаментальные науки»Кафедра «Математическая физика и вычислительная математика»В.А. Кутыркин, А.Ю. БушуевЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ ИФОРМАЛЬНЫХ ЯЗЫКОВЭлектронное учебное изданиеМетодические указания к решению задачпо дисциплине «Теория автоматов и алгоритмические языки»Москва(С) 2014 МГТУ им. Н.Э. БАУМАНАУДК 518.5 (075.8)ББК 22.12Рецензент: доц., к.т.н.Кутыркин В.А., Бушуев А.Ю.Элементытеорииконечныхавтоматовиформальныхязыков.Электронное учебное издание.

- М.: МГТУ имени Н.Э. Баумана, 2014. 48 с.Издание содержит основные понятия теории конечных автоматов иформальных языков. Предварительно приводятся необходимые сведения изтеории графов, необходимые для способов компьютерного задания инаглядного представления конечных автоматов и формальных языков.Излагаются основные методы анализа и синтеза конечных автоматов.Приведён разбор типовых задач и условия типовых индивидуальных домашнихзаданий.Издание рассчитано на студентов, прослушавших курс по дисциплине«Дискретная математика и математическая логика».Для студентов МГТУ имени Н.Э.

Баумана по направлению бакалавриата«Математика и компьютерные науки».Рекомендованоучебно-методическойкомиссиейфакультета«Фундаментальные науки» МГТУ им. Н.Э. БауманаЭлектронное учебное изданиеКутыркин Владимир АндреевичБушуев Александр ЮрьевичЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ И ФОРМАЛЬНЫХ ЯЗЫКОВ.© 2014 МГТУ имени Н.Э. БауманаОглавлениеВведение.............................................................................................................................41.Форамальные языки .......................................................................................................62. Лексикографический порядок. Словари формальных языков ..................................83.

Элементы теории конечных графов ...........................................................................153.1. Ориентированные графы. Деревья. Логические сети ........................................153.2. Неориентированные графы. Контактные сети ...................................................183.3. Конечные мульти-орграфы. Язык конечного мульти-орграфа ........................194. Детерминированные и недетерминированные автоматы ........................................224.1. Способы задания конечных автоматов Мили ....................................................244.2. Минимизация конечного автомата Мили по состояниям .................................264.3 Алгоритм минимизации конечного автомата Мили по состояниям .................275.

Дискретные преобразователи .....................................................................................325.1. Логические схемы из функциональных элементов ...........................................325.2. Контактные схемы ................................................................................................355.2.1. Синтез контактной схемы методом каскадов ..............................................375.2.2.

Дерево анализа контактной схемы ...............................................................386. Вопросы для самопроверки ........................................................................................417. Индивидуальные домашние задания .........................................................................42Приложение 1 ...................................................................................................................45Литература ........................................................................................................................474ВведениеВ представленных методических указаниях излагаются основные понятия теорииавтоматов и формальных языков. Для формальных языков приводятся методы построенияих словарей и поиска слова в словаре по его номеру.

Такие методы полезны для работы сформальными языками в прикладных компьютерных задачах. Изложение методов анализаи синтеза конечных автоматов предваряется введением в теорию графов, основныепонятия которой необходимы для компьютерных способов задания и наглядногопредставления конечных автоматов. После этого даны основные определения и понятиятеории автоматов с описанием алгоритмов оптимального построения конечных автоматов.Особое внимание уделено задачам анализа и синтеза для автоматов, являющихсядискретными преобразователями, поскольку на их основе реализуются способы синтезаобщих конечных автоматов.

Для решения задачи анализа контактной схемы вводитсяособый граф, называемый деревом анализа контактной схемы. Этот граф позволяетперечислить все простые пути в контактной схеме, связывающие её вход и выход, чтопозволяет вычислить пропускную способность контактной схемы.Изложение методических указаний сопровождается многочисленными примерамипо решению типовых задач.

Для улучшения освоения материала приведены упражнения,позволяющие закрепить основные понятия и методы изложения. В заключение приведеныусловия задач для выполнения индивидуальных домашних заданий по первой части курсадисциплины «Теория автоматов и алгоритмические языки», изучаемой студентами понаправлению бакалавриата «Математика и компьютерные науки». Для более полногоизучения автоматных, регулярных языков и алгоритмических языков можно ознакомитьсяс учебным пособием [1] и книгой [2], для знакомства с магазинными автоматами кучебнику [3]. Кроме того, для получения практических навыков полезен задачник [4].Кратко, представленные методические указания характеризуются следующимобразом.Цель домашних заданий – практическое освоение способов упорядоченияформальных языков и методов анализа и синтеза конечных автоматов.

Для этого вметодических указаниях приводятся примеры создания словарей формальных языков испособов выбора слов из этих словарей. Практическому усвоению этого материаласпособствуют сопровождающие изложение упражнения. Для правильного освоенияметодов анализа и синтеза конечных автоматов излагаются предварительные сведения изОглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю. Бушуев5теории графов, поскольку при компьютерном задании автоматов необходимо иметьспособы представления их структуры. Приводимые далее методы анализа и синтезаконечныхавтоматовопираютсянаэтисведения,чтопозволяетнагляднопроиллюстрировать методы анализа и синтеза конечных автоматов на конкретныхпримерах. Для закрепления этих методов предложены соответствующие упражнения.Краткая характеристика объекта изучения.

В предлагаемых методическихуказаниях приводятся основные понятия и структуры формальных языков и теорииавтоматов, которые необходимы при компьютерной работе с этими объектами. Впредставленный теоретический материал позволит студенту грамотно выполнитьдомашние задания.Задачи и порядок выполнения домашних заданий. Настоящие методическиеуказания содержат раздел «Индивидуальные домашние задания», в котором перечисленыусловия задач, которые студент должен решить в процессе освоения дисциплины.Приведённые в настоящих методических указаниях примеры иллюстрируют способыотчёта о решении предложенных задач.Вопросы для самоконтроля.

Для самоконтроля усвоения представленногоматериала в настоящих методических указаниях выделен раздел «Вопросы длясамопроверки».Форма отчета по выполнению домашних заданий. При оформлении выполненныхдомашних заданий студент должен представить решение задач в следующем виде.На титульном листе приводится название: Домашние задания по дисциплине«Теория автоматов и алгоритмические языки», вариант. Ниже указывается исполнительзадания с указанием группы и факультета.

В правом нижнем углу указываетсяпреподаватель, ведущий дисциплину, и графа об оценке выполнения домашнего задания.Содержательная часть выполнения домашнего задания должна последовательно излагатьрешения поставленных задач с предварительной формулировкой условий задач.Оглавление oglavЭлементы теории автоматов и формальных языковВ.А. Кутыркин, А.Ю.

Бушуев61.Форамальные языкиИсходным понятием для введения формальных языков является понятии математическогознака, далее, просто – знака. Знак – это нечленимый элемент для построения строк (слов,символов) формального языки, т.е. знак является своеобразным атомом. Поэтому знакудовлетворяет закону тождества, благодаря чему возможны точные его теоретическиекопии и становится возможным однозначное теоретическое прочтение строк из негосконструированных(записанных).Строкаполучаетсяприпомощиконечной,последовательной, слева направо, подряд записи знаков.