Абстрактная и структурная теории конечных автоматов. Структура операционного устройства. Способы задания автоматов, страница 8

в) Находим разбиение p₃ множества состояний а₁,а₂,а₃,а₄,а₅,а₆,а₇,а₈ на 3‑совместимые классы. Оно находится по таблице (рис.1.8) аналогично тому, как были найдены 2-совместимые классы.

D₁={а₁,а₂}, D₂={а₃}, D₃={а₄,а₅}, D₄={а₆}, D₅={а₇}, D₆={а₈}.

Подставим в таблицу переходов (рис.1.6) вместо состоянийа₁¸а₈ соответствующие значения D₁, D₂, D₃, D₄, D₅, D₆. После подстановки получим таблицу, изображенную на рис.1.9.

г) Находим разбиение p₄ множества состояний а₁,а₂,а₃,а₄,а₅,а₆,а₇,а₈ на 4‑совместимые классы: E₁={а₁,а₂}, E₂={а₃}, E₃={а₄,а₅}, E₄={а₆}, E₅={а₇}, E₆={а₈}.

Разбиение p₄  совпадает с разбиением p₃ , следовательно, разбиение p₃ предельное.

2.  Находим множество состояний минимального автомата

={а₁,а₃,а₄,а₆,а₇,а₈}.

3. Из таблицы (рис.1.6) вычеркиваем состояния, не вошедшие в множество, а в оставшихся столбцах таблицы переходов все состояния заменяем на эквивалентные из множества (а₁а₂,  а₄а₅).

	а1	а3	а4	а6	а7	а8
z1	w1	w1	w2	w2	-	w2
z2	w2	-	w1	w1	w1	w1

	а1	а3	а4	а6	а7	а8
z1	а1	а8	а1	а4	а6	а4
z2	а4	а1	а6	а3	а1	а1

В результате получим таблицы переходов и выходов, изображенные на рис.1.10.

Рис.1.10.  Таблицы минимального автомата

Причем, если в таблице выходов вычеркивается столбец, имеющий на пересечении с i-ой строкой определенный сигнал w_j, а в оставшемся столбце, отмеченном состоянием, эквивалентным состоянию, отмечающем вычеркнутый столбец, на пересечении с i-ой строкой проставлен прочерк, то в оставшемся столбце вместо прочерка необходимо записать сигнал w_j.               

2.  ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕ ОПЕРАЦИОННЫХ УСТРОЙСТВ

2.1.  Структура операционного устройства

В любой системе обработки цифровой информации можно выделить операционный и управляющий блоки. Такой подход упрощает проектирование, а также облегчает понимание процесса функционирования вычислительного устройства. Данный процесс состоит из того, что операционный блок производит определенные операции преобразования информации под управлением сигналов, вырабатываемых управляющим блоком. Эта распределенная во времени последовательность управляющих сигналов, порождающая в операционном блоке нужную последовательность элементарных преобразований информации, составляет микропрограмму операции.

Представим центральную часть ЭВМ (процессор), называемую в дальнейшем операционным устройством, как совокупность управляющего и операционного автоматов (рис.2.1).

 

D                  R

Y                                            X

G

Операционное  устройство