В.П.Битюцкий

И.В.Хмелевский

Проектирование автоматов

Федеральное агентство по образованию

ГОУ ВПО «Уральский государственный технический университет -УПИ»

В.П.Битюцкий

И.В.Хмелевский

Проектирование автоматов

Учебное пособие

Научный редактор– проф., д-р техн.наук В.И.Кузякин

Екатеринбург

2006

УДК 519.713.001.63

ББК 32.815-02

Б66

Р е ц е н з е н т ы

Кафедра информатики Уральского государственного горного университета (зав.кафедрой проф., д-р техн. наук М.Б.Носырев);

доц., канд.техн.наук Г.Б.Захарова (УрО РАН).

Авторы: В. П. Битюцкий И.В.Хмелевский

Б66 Проектирование автоматов: учебное пособие /В.П. Битюцкий, И.В.Хмелевский. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006. 93 с.

ISBN 5-318-00537-3

Приводятся основные понятия и утверждения из теории абстрактных и структурных автоматов, вопросы их минимизации, композиции, декомпозиции и синтеза. Решение задачи проектирования автоматов доведено до синтеза схемы автомата в заданном базисе.

Рассмотрены вопросы учёта временных характеристик элементов, гонки и состязания в сетях, способы противогоночного кодирования состояний автомата.

Отдельный раздел посвящен автоматам-распознавателям, для чего рассмотрены формальные грамматики и языки, которые понимают автоматы.

Библиогр. : 5 назв. Табл. 50. Рис. 32.

УДК 519.713.001.63

ББК 32.815-02

ISBN 5-318-00537-3 ГОУ ВПО «Уральский государственный

технический университет-УПИ», 2006

 В.П. Битюцкий, И.В.Хмелевский 2006

Оглавление

Введение 3

1. Абстрактные автоматы 5

1.1. Эквивалентность автоматов 7

1.2. Минимизация автоматов 11

1.2.1. Минимизация полностью определенного автомата 11

1.2.2. Минимизация частичного автомата 12

1.3. Композиция автоматов 18

1.3.1. Параллельное соединение 18

1.3.2. Последовательное соединение 18

1.3.3. Соединение с обратной связью 19

1.3.4. Соединение в сеть 19

1.4 Декомпозиция автомата 22

1.4.1. Задача декомпозиции 22

1.4.2. Разбиения со свойствами подстановки 23

1.4.3. Метод декомпозиции 25

1.5. Упражнения 29

Эквивалентность автоматов 29

Минимизация полностью определённого автомата. 31

Декомпозиция автоматов 32

2. Структурные автоматы 35

2.1. Автоматная полнота и теорема В.М.Глушкова 35

2.2. Гонки в автомате 38

2.2.1. Кодирование состояний 38

2.2.2. Понятие о гонках. Противогоночное кодирование 38

2.3. Проектирование автомата 40

2.4. Упражнение 44

Кодирование 44

Синтез автомата 46

3. Синтез схем 47

3.1. Определения 47

3.2. Функциональная полнота базиса 48

3.2.1. Классы функций 48

3.2.2. Монотонные функции 48

3.2.3. Самодвойственные функции 49

3.2.4. Линейные функции 50

3.2.5. Функции, сохраняющие константу 51

3.2.6. Функциональная полнота 52

3.3. Топологические ограничения в схемах 54

3.3.1. Плоские схемы 55

3.3.2. Ограничения на глубину связи в схеме 56

3.4. Методы синтеза схем 60

3.4.1. Метод факторизации 60

3.4.2. Метод декомпозиции 60

3.4.3. Синтез схем в классическом базисе. 63

3.4.4. Синтез схем в монофункциональном базисе. 63

3.5. Упражнения 65

Функциональная полнота 65

Синтез схем 65

4. Эксперименты над автоматами 67

4.1. Построение диагностических деревьев 67

4.2. Диагностические и установочные эксперименты 68

4.2.1. Дерево преемников 69

4.2.2. Диагностический эксперимент 70

4.2.3. Установочный эксперимент 74

4.3. Упражнения 74

Диагностические эксперименты 74

Установочные эксперименты 76

5. Формальные грамматики 76

5.1. Языки и порождающие их грамматики 76

5.2. Примеры фрагментов описаний в языках программирования. 80

5.3. Порождающая грамматика 81

5.4. Классы языков и грамматик 84

5.5. Язык, понимаемый устройством 85

5.6. Автоматные языки 86