Лекции (998707), страница 11
Текст из файла (страница 11)
A 2 2={ a5, a7, a8}; A 3 2={ a3, a4, a6, a9, a11}; A 4 2={ a10, a12}
Таблица 3.2.
| Xi | ak, A sp | |||||||||||
| A 11 | A 12 | |||||||||||
| a1 | a2 | a5 | a7 | a8 | a3 | a4 | a6 | a9 | a10 | a11 | a2 | |
| X1 | A 12 | A 12 | A 12 | A 12 | A 12 | A 11 | A 11 | A 11 | A 11 | A 11 | A 11 | A 11 |
| X2 | A 11 | A 11 | A 12 | A 12 | A 12 | A 12 | A 12 | A 12 | A 12 | A 11 | A 12 | A 11 |
Таблица 3.3.
| Xi | ak, A sp | |||||||||||
| A 21 | A 22 | A 23 | A 24 | |||||||||
| a1 | a2 | a5 | a7 | a8 | a3 | a4 | a6 | a9 | a11 | a10 | a12 | |
| X1 | A 24 | A 24 | A 23 | A 23 | A 24 | A 22 | A 22 | A 22 | A 22 | A 22 | A 21 | A 21 |
| X2 | A 22 | A 22 | A 23 | A 23 | A 23 | A 23 | A 23 | A 23 | A 23 | A 23 | A 22 | A 22 |
Таблица 3.4.
| Xi | ak, A sp | |||||||||||
| A 31 | A 32 | A 33 | A 34 | A 35 | ||||||||
| a1 | a2 | a5 | a7 | a8 | a3 | a4 | a6 | a 9 | a 11 | a 10 | a 12 | |
| X1 | A 35 | A 35 | A 32 | A 32 | A 34 | A 33 | A 33 | A 33 | A 33 | A 33 | A 31 | A 31 |
| X2 | A 32 | A 32 | A 34 | A 34 | A 34 | A 34 | A 34 | A 34 | A 34 | A 34 | A 33 | A 33 |
Продолжая аналогичную процедуру и далее, соответственно получим класс эквивалентности П3. Таблицы для всех этих классов: для П2 - табл. 3.3., для П3 - табл. 3.4.
Из табл. 3.5. видно, что П3 = П, откуда можно составить совмещенную таблицу уже минимизированного автомата (табл. 3.5.).
Используя рассмотренную процедуру по отношению к автомату, представленному графом на рис. 3.14., легко показать, что тот автомат после минимизации полностью переходит в автомат Мили, граф которого помещен на рис. 3.15.
Аналогичную процедуру минимизации можно провести и для автомата Мура.
Таблица 3.5.
| Xi | a k | ||||
| a 1 | a 5 | a 8 | a 3 | a 10 | |
| X1 | a 10 Y1 | a 3 Y1 | a 10 Y1 | a 5 Y2 | a 1 Y2 |
| X2 | a 5 Y2 | a 3 Y2 | a 3 Y2 | a 3 Y1 | a 8 Y1 |
Рис. 3.14. Рис. 3.15.
3.3. Структурный синтез конечных автоматов.
Вслед за этапом абстрактного синтеза автоматов, заканчивающимся минимизацией числа состояний, следует этап структурного синтеза. Его целью является построение схемы, реализующей автомат из логических элементов заданного типа и триггеров. Если абстрактный автомат был лишь математической моделью дискретной системы, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутреннее устройство на уровне структурной схемы.
В
отличие от абстрактного автомата, имеющего один вход и выход, структурный автомат имеет много входов 
и выходов 
и реализуется на элементарных автоматах 
.
Элементарный автомат (ЭА) имеет только два состояния 0 и 1, и реализуется на триггере. Входные и выходные сигналы принимают двоичное значение. Структурным синтезом, занимается структурная теория автоматов. Её основной задачей является нахождения общих принципов построения структурных схем автоматов на основе элементарных автоматов, принадлежащих заранее заданному конечному числу типов.
3.3.1 Этапы структурного синтеза автоматов.
-
Кодирование символов алфавитов абстрактного автомата.
-
Получение кодированных таблиц переходов и выходов.
-
Определение функций внешних переходов.
-
Выбор типа элементарных автоматов.
-
Получение функции возбуждения элементарных автоматов и функции выходов.
-
Построение принципиальной схемы автомата.
3.3.2. Кодирование символов алфавитов абстрактных автоматов.
Поскольку входные и выходные сигналы структурного автомата принимают двоичные значения, то каждый входной xj и выходной yi сигналы абстрактного автомата кодируются двоичными векторами длины nC и nZ. 
Так же кодируется выходной сигнал.
Очевидно, что число разрядов векторов находится из:
;
Аналогичным образом осуществляется кодировка символов выходного алфавита.
где 
- количество элементарных автоматов.
Результатом кодирования является определение таких характеристик структурного автомата, как число входов nC, число выходов nZ и число элементарных автоматов. Кроме того, устанавливается соответствие между значениями входных и выходных сигналов и состояниями абстрактного и структурного автомата.
С![]()
труктурная схема автомата.
Переход i-ого элементарного автомата в следующее состояние определяется функцией внешних переходов 
. Состояние i-ого элементарного автомата является функцией состояний всех автоматов.
как его, так и внешних по отношению к нему, чем и определяется слово «внешние» в названии функции переходов. В векторной форме функции внешних переходов выглядит более компактно.
Переход элементарных автоматов в следующее состояние осуществляется под воздействием входных сигналов, называемых сигналами возбуждения: 
Сигналы возбуждения входов элементарных автоматов формируются в соответствии со значением функций возбуждения элементарных автоматов:
Они формируются в комбинационной схеме. Выходные сигналы формируются комбинационной схемой функций выходов:
или в векторной форме
Структурный автомат, как и абстрактный автомат, может быть автоматом Мура или Мили в зависимости от способа формирования выходных сигналов.
- для автомата Мура.
- для автомата Мили.
В автомате Мура входные сигналы С1,С2…
не используются при формировании выходных сигналов.
Проблемы возникающие при кодировании.
Кодирование любого объекта из общего числа объектов, равному n, может быть выполнено:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
