Занятие 4.1. Синтез комбинационных автоматов
Задача 45
Заданы два КА и в виде автоматных таблиц. Построить КА , эквивалентный последовательному соединению автоматов и .
Решение
1. Нарисуем схему последовательного соединения автоматов и .

2. Зададим КА эквивалентный последовательному соединению автоматов и .
a) Входной алфавит .
b) Выходной алфавит .
c) Множество состояний .
d) Зададим автоматную таблицу автомата , предполагая, что автоматы и — автоматы без задержки.

Задача 46
Задан КА с двумя входами. Построить КА эквивалентный включению исходного автомата с обратной связью.

Решение
1. Нарисуем схему включения исходного автомата с обратной связью.

2. Зададим КА эквивалентный включению исходного автомата с обратной связью.
a) Входной алфавит .
b) Выходной алфавит .
c) Множество состояний .
d) Зададим автоматную таблицу автомата , предполагая, что автомат — автомат без задержки.

Задача 47
Синтезировать КА в виде схемы из логических элементов, преобразующий знаки входного алфавита в знаки выходного алфавита таким образом, что , а .
Решение
1. Составляем автоматную таблицу по описанию автомата из условия задачи.

2. Так как получена автоматная таблица соответствующая комбинационному автомату, то применяем методику синтеза комбинационных автоматов.
3. Выбираем автоматный базис, реализующий функционально полную систему операций в булевой алгебре: .
4. Выполняем кодирование входного и выходного алфавита в виде строк длины над двоичным алфавитом .
a) , .
b) Задаём код

5. Задаём таблицу истинности для булевых функций, описывающих работу автомата с учётом кодирования алфавитов.

6. Представляем функции из таблицы истинности в виде выражений в выбранном базисе операций, используя СКНФ:
7. Реализуем полученное выражение в виде схемы из логических элементов.

Замечание: Построенная указанным методом схема может не работать из-за состязания логических элементов, поэтому необходимо выполнить пункт 8, применив методику синтеза комбинационных схем свободных от критических состязаний.
Задача 48
Заданы 2 КА и в виде автоматных таблиц. Построить КА , эквивалентный параллельному соединению автоматов и с раздельным входом.

Занятие 4.2 Синтез асинхронных автоматов
Задача 49
Синтезировать асинхронный автомат в виде схемы из логических элементов, распознающий язык , заданный регулярным выражением: .
Решение
1. Задаём источник, соответствующий регулярному выражению .

2. Детерминируем заданный источник.

3. Строим гомоморфизм, заданный на множествах состояний исходного источника.

4. Зададим КА в виде автоматной таблицы, где выходной алфавит определим следующим образом:
0 – принятая строка ещё не распознана,
1 – принятая строка принадлежит языку,
2 – принятая строка не принадлежит языку.

5. Выбираем автоматный базис, реализующий функционально полную систему операций в булевой алгебре: .
6. Выполняем кодирование алфавитов автомата в виде строк длины над двоичным алфавитом .
a) , , .
b) , , .
c) Задаём код:

7. Задаём таблицу истинности для булевых функций, описывающих работу автомата с учётом кодирования алфавитов.

8. Представляем функции из таблицы пункта 7 в виде выражений в функционально полном базисе .

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

Занятие 4.3 Синтез синхронных автоматов
Задача 50
Синтезировать КА в виде схемы из логических элементов, повторяющий на выходе знаки входного алфавита , когда на управляющем входе знак и сохраняющий предпоследний принятый знак алфавита, когда на управляющем входе знак , если .
Решение
1. Изобразим схему работы искомого автомата.

2. Определим множество состояний , где:
состояние означает, что запомнены знаки ,
состояние означает, что запомнены знаки ,
состояние означает, что запомнены знаки ,
состояние означает, что запомнены знаки .
3. Составляем автоматную таблицу по описанию функционирования автомата.

4. Из анализа таблицы заключаем, что автомат синхронный, так как, например, состояние не устойчиво по входному знаку .
5. Выбираем автоматный базис, реализующий функционально полную систему операций в булевой алгебре: .
6. Выполняем кодирование алфавитов автомата в виде строк длины над двоичным алфавитом .
a) , , .
b) Задаём код:

7. Задаём таблицу истинности для булевых функций, описывающих работу автомата с учётом кодирования алфавитов.

8. Представляем функции из таблицы пункта 7 в виде выражений в функционально полном базисе .

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

СПИСОК ЛИТЕРАТУРЫ

1. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс: Пер. с англ. – М.: Радио и связь, 1988.
2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – 2-е изд., перераб. и доп. – М.: Энергоатомиз-дат, 1988. – 480 с.: ил.
3. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учебное пособие для втузов. – СПб.: Политехника, 1996. – 885 с.
4. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. М.: Наука, 1985.
5. Горбатов В.А. Основы дискретной математики: Учебное пособие для студентов вузов. – М.: Высш.шк, 1986.
6. Брой М. Информматика. Теоретическая информатика, алгоритмы и структуры данных, логическое программирование, объектная ориентация: В 4-х ч. Ч. 4. – М.: Диалог-МИФИ, 1998. – 224 с.
7. Братчиков И.Л. Синтаксис языков программирования. – М.: Наука, 1975. – 232 с.

Учебное издание

Выхованец Валерий Святославович

Сборник задач по теории автоматов
Учебное пособие для вузов

Редактор О. Д. Выхованец
Компьютерный набор и верстка А. С. Лупу
Компьютерная графика А. С. Лупу