Файл: Методические указания к решению задач по дисциплине Теория автоматов и алгоритмические языки.pdf

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

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

Оглавление
Введение ............................................................................................................................. 4 1.Форамальные языки ....................................................................................................... 6 2. Лексикографический порядок. Словари формальных языков .................................. 8 3. Элементы теории конечных графов ........................................................................... 15 3.1. Ориентированные графы. Деревья. Логические сети ........................................ 15 3.2. Неориентированные графы. Контактные сети ................................................... 18 3.3. Конечные мульти-орграфы. Язык конечного мульти-орграфа ........................ 19 4. Детерминированные и недетерминированные автоматы ........................................ 22 4.1. Способы задания конечных автоматов Мили .................................................... 24 4.2. Минимизация конечного автомата Мили по состояниям ................................. 25 4.3 Алгоритм минимизации конечного автомата Мили по состояниям ................. 27 5. Дискретные преобразователи ..................................................................................... 32 5.1. Логические схемы из функциональных элементов ........................................... 32 5.2. Контактные схемы ................................................................................................ 35 5.2.1. Синтез контактной схемы методом каскадов .............................................. 37 5.2.2. Дерево анализа контактной схемы ............................................................... 38 6. Вопросы для самоконтроля ........................................................................................ 41 7. Индивидуальные домашние задания ......................................................................... 43
Приложение ...................................................................................................................... 45
Литература ........................................................................................................................ 47

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

5
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев теории графов, поскольку при компьютерном задании автоматов необходимо иметь способы представления их структуры. Приводимые далее методы анализа и синтеза конечных автоматов опираются на эти сведения, что позволяет наглядно проиллюстрировать методы анализа и синтеза конечных автоматов на конкретных примерах. Для закрепления этих методов предложены соответствующие упражнения.
Краткая характеристика объекта изучения. В предлагаемых методических указаниях приводятся основные понятия и структуры формальных языков и теории автоматов, которые необходимы при компьютерной работе с этими объектами. В представленный теоретический материал позволит студенту грамотно выполнить домашние задания.
Задачи и порядок выполнения домашних заданий. Настоящие методические указания содержат раздел «Индивидуальные домашние задания», в котором перечислены условия задач, которые студент должен решить в процессе освоения дисциплины.
Приведѐнные в настоящих методических указаниях примеры иллюстрируют способы отчѐта о решении предложенных задач.
Вопросы для самоконтроля. Для самоконтроля усвоения представленного материала в настоящих методических указаниях выделен раздел «Вопросы для самоконтроля».
Форма отчета по выполнению домашних заданий. При оформлении выполненных домашних заданий студент должен представить решение задач в следующем виде.
На титульном листе приводится название: Домашние задания по дисциплине
«Теория автоматов и алгоритмические языки», вариант. Ниже указывается исполнитель задания с указанием группы и факультета. В правом нижнем углу указывается преподаватель, ведущий дисциплину, и графа об оценке выполнения домашнего задания.
Содержательная часть выполнения домашнего задания должна последовательно излагать решения поставленных задач с предварительной формулировкой условий задач.

6
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
1.Формальные языки
Исходным понятием для введения формальных языков является понятие математического
знака, далее, просто – знака. Знак – это нечленимый элемент для построения строк (слов, символов) формального языки, т.е. знак является своеобразным атомом. Поэтому знак удовлетворяет закону тождества, благодаря чему возможны точные его теоретические копии и становится возможным однозначное теоретическое прочтение строк из него сконструированных (записанных). Строка получается при помощи конечной, последовательной, слева направо, подряд записи знаков. При записи строки каждый записываемый знак характеризуется своим местом в строке, можно сказать номером места
(позиции) или просто – номером. Место начальной буквы имеет номер 1, номер места следующей буквы, если таковая имеется, равен 2 и т.д. Длина слова определяется номером последней буквы в слове.
Для обозначения строк могут использоваться знаки или другие строки, становящиеся символами.
Особо выделяется пустая строка, не имеющая в своей записи ни одной буквы. Для записи пустой строки используется символ

Определение 1.1.(знакового алфавита). Алфавит знаков – это строка, начальный
(заключительный) знак которой равен

(

), и между этими знаками (начальным и заключительным), последовательно, через знак запятой, перечислены попарно различные знаки этого алфавита. Такой алфавит обязан содержать хотя бы один знак.►
Пример 1.1(знаковых алфавитов).
а)
, ,,
a b


– алфавит из 3-х знаков;
б) В алфавите
, _,
a
b


знак _ играет роль пробела.►
Замечание 1.1 (об алфавитных знаках). Для обозначения алфавита используются дважды подчѐркиваемые знаки-символы. Если A – обозначение алфавита, то A – обозначение совокупности знаков этого алфавита, в частности,


, , , ,
a b b b a
– совокупность из двух знаков алфавита
,
A
a b
 

. Алфавит устанавливает «старшинство» среди своих знаков.

7
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Самый младший – первый и т.д. Совокупность A знаков алфавита A будет называться
квази-алфавитом.►
Определение 1.2 (формального языка). Пусть A – алфавит знаков. Тогда все строки, в записи которых участвуют знаки только этого алфавита, образуют позитивный язык для этого алфавита. Такой позитивный язык обозначается символом A

. Добавив к языку A

пустую строку, получим универсальный язык для этого алфавита, обозначаемый
*
A . Язык
*
A – совокупность всех A -строк. Любая подсовокупность универсального языка называется формальным A -языком.►
Большие тексты состоят из последовательной записи многих строк. Поэтому при введении формальных языков определяют особую операцию присоединения строк, называемую сцеплением или конкатенацией строк.
Определение 1.3 (сцепления строк). Пусть
x
и y – строки. Сцепить строку
x
со строкой
y – это значит приписать к слову
x
справа слово
y . Результат такого сцепления обозначается выражением
x
y

, где

– символ-знак сцепления (конкатенации) строк.
По определению, строки
x

и
x

совпадают со строкой
x
(

– пустая строка).►
Согласно такому определению
aab
bb
aabbb


Замечание 1.2. Если
x
и y – строки, то (
x
y

) результат сцепления строк
x
и y , совпадающий с результатом
x
y

. Для операции сцепления строк справедливо тождество ассоциативности, т.е.
(
)
(
)
x
y
z
x
y
z
    
. Из этого тождества следует сочетательный закон сцепления строк. Поэтому скобки при сцеплении строк можно не указывать.►
Определение 1.4(буквенного алфавита и его слов). Список из попарно различных непустых строк, в записи которых не участвует знак запятой, может образовывать буквенный алфавит, где буквы – это строки из этого списка. Пусть
1
,...,
n
y
y


– такой список попарно различных букв (угловая скобка

– начало списка, скобка

– его окончание). Список
1
,...,
n
y
y


является буквенным алфавитом, если любое сцепление его букв допускает однозначное побуквенное чтение. Следовательно, если
1 1
,...,
, ,...,
k
m
u
u v
v

8
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев это буквы этого списка и
1 1
k
m
u
u
v
v
 
  
, то k m

и
1 1
u
v

и
1 1
,...,
k
m
u
v
u
v


Результат сцепления букв алфавита называется словом в этом алфавите.►
Замечание 1.3. Как и для знаковых алфавитов, вследствие однозначности прочтения, для буквенных алфавитов определяются соответствующие понятия универсальных и формальных языков. Далее, поскольку алфавит знаков также можно рассматривать как буквенный алфавит, для знаковых и буквенных алфавитов используется общий термин –
алфавит.►
2. Лексикографический порядок. Словари формальных языков
На протяжении настоящего раздела используется алфавит
1
,...,
k
A
a
a

, для которого A
– символ совокупности его букв. Совокупность A будет называться квази-алфавитом, число
( )
i
A
a
i

N
(
1 i
k
 
) номером буквы
i
a в алфавите
A
или
A
-номером этой буквы.
Следовательно, далее
|
| |
|
A
A
k


– размер этого алфавита.
Для пустого слова, которое является пустой строкой, как и ранее, будет использоваться символ

. Совокупность всех слов, включая пустое, записанных из букв алфавита A (совокупность A -слов), образует универсальный язык A

, любой подъязык которого называется формальным A -языком. В частности, если из универсального языка
A

исключить пустое слово, то такой формальный
A -язык называется позитивным A -
языком и для него используется обозначение A

Если
x
и y – два слова, то выражение
x
y

обозначает результат сцепления слова
x
со словом y (

– знак операции сцепления или конкатенации слов). Например,
_
_
aab
bb
aab bb


и
x
x
x
 
Для универсального языка A

создаѐтся особый словарь
(
)
A
A

Dc
, называемый
натуральным
A -словарѐм.
Для создания такого словаря используется
лексикографический A -порядок «старшинства» слов в языке A

, индуцированный
(наведѐнный) алфавитом A . Если два A -слова имеют различные длины и
| | |
|
x
y

, то, согласно такому порядку, слово
y
«старше» слова x . Если же их длины одинаковы и,