Задачи для самостоятельного решения
Выяснить, какие из следующих функций являются детерминированными:
а)
б)
в)
Ответы: а) Детерминированная; б) детерминированная; в) недетерминированная.
Выяснить, какие из следующих функций являются ограниченно детерминированными:
а)
б)
в)
Ответы: а) Является; б) не является; в) является.
Определить количество классов эквивалентности множества вершин дерева следующих функций:
а)
(mod
б)
в)
Ответы: а) 3; б) 4; в) 4.
§ 4.4. Синтез автоматов
Под синтезом автоматов мы понимаем построение автоматов, удовлетворяющих заданному свойству или выполняющий заданные функции. Ранее был построен элемент задержки (см. рис.4.26),
к
оторый
сдвигает входную последовательность
на один такт:
при
Соединяя последовательно два элемента
задержки (см. рис. 4.27), мы получим сдвиг
на два такта:
при
А
втоматы
и
можно соединять последовательно (см.
рис. 4.28)
в
случае, если
При этом получается автомат
у которого
Параллельное соединение автоматов (см.
рис. 4.29)
приводит
к появлению автомата
где
П
усть
конечный автомат. Если
и
то входной символ
можно закодировать двоичной
последовательностью длины
а именно:
и т.д. Аналогично, если
и
то выходные символы
могут быть представлены двоичными
последовательностями длины
Автомат
таким образом, становится устройством,
перерабатывающим двоичную информацию
(см. рис. 4.30).
В
ыходы
представляют собой булевы функции от
входов
где
Эти функции можно реализовать с помощью
схем, содержащих стандартные булевы
элементы и элемент задержки (см. рис.
4.31):
Пример. Рассмотрим устройство, осуществляющее сложение двух двоичных последовательностей с переносом разряда. Например,
-
0
1
0
0
1
0
1
1
0
1
0
. . .
1
0
1
1
1
0
1
0
1
1
0
. . .
1
1
1
1
0
1
1
0
0
1
1
. . .
Таким
образом,
П
оложим
Тогда
если среди чисел
не более одного равны 1,
в противном случае. Нетрудно видеть,
что
Теперь мы можем изобразить схему
устройства (см. рис. 4.32).
Упражнение
12. Дан алфавит
Построить автомат, отыскивающий во
входной последовательности подслово
и заменяющий после этого все символы
символом
Например,
Р
ешение.
Пусть
обозначает начальное состояние,
– состояние, в которое автомат перейдёт,
получив на входе символ
– символ
после
– финальное состояние. Изобразим теперь
диаграмму Мура искомого автомата (см.
рис. 4.33).
Упражнение
13. Выяснить,
существует ли конечный автомат
с алфавитами
такой, что:
а)
б)
Решение.
а) Такого автомата не существует:
действительно, у входных слов 011 и 010
совпадают первые две буквы, а выходные
слова 101 и 111 этим свойством не обладают.
Другими словами, функцию
нельзя продолжить до детерминированной
функции
б) Условие детерминированности здесь выполнено. Докажем, что автомат, удовлетворяющий данным условиям, существует. Построим фрагмент информационного дерева (см. рис 4.34).
В
ершины
и
не эквивалентны. Если ребро
будет помечено символом 0, то
и
если же его пометить символом 1, то всё
равно
Пусть
Получим следующий граф (см. рис. 4.35).
Замыкая произвольным образом повисшие стрелки этой диаграммы, получим диаграмму Мура автомата (см. рис. 4.36)
У
пражнение
14. Построить
автомат с наименьшим числом состояний,
для которого
Решение. Построим информационное дерево (см. рис. 4.37):
О
чевидно,
Значит, количество классов эквивалентности
информационного дерева (т.е. количество
состояний автомата) не меньше 3. Полагаем
и получаем диаграмму Мура искомого
автомата (см. рис. 4.38).
П
унктиром
обозначены стрелки, добавленные для
обеспечения полноты диаграммы. Эти
стрелки можно направить и в другие
кружочки.