Конечные автоматы ч.2
Описание файла
PDF-файл из архива "Конечные автоматы ч.2", который расположен в категории "". Всё это находится в предмете "вычислительные сети и системы" из 7 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "вычислительные системы и микропроцессоры" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Минимизация числа внутренних состояний абстрактных автоматовПример минимизации автомата Мили, заданного совмещенной таблицей переходов и выходовakXia1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12a10 a12 a5 a7 a3 a7 a3 a10 a7 a1 a5 a2Y1 Y1 Y2 Y2 Y1 Y2 Y1 Y1 Y2 Y2 Y2 Y2a5 a7 a6 a11 a9 a11 a6 a4 a6 a8 a9 a8Y2 Y2 Y1 Y1 Y2 Y1 Y2 Y2 Y1 Y1 Y1 Y1X1X2Одношагово-эквивалентные (1-эквивалентные) состояния: новый алфавит П1 ={ A1 1, A2 1};A1 1={ a1, a2, A5, a7, a8}; A2 1={ a3, a4, a6, a9, a10, a11, a12}.ak, AspA11XiA12a1a2a5a7a8a3a4a6a9a10a11A1211111111111A11X1 A2A2A2A2A2A1A1A1A1A1A1X2 A11 A11 A12 A12 A12 A12 A12 A12 A12 A11 A12 A112-эквивалентные состояния: новый алфавит П2={ A 1 2, A 2 2, A 3 2, A 4 2};A 1 2={ a1, a2}; A 2 2={ a5, a7, a8}; A 3 2={ a3, a4, a6, a9, a11}; A 4 2={ a10, a12}.ak, AspA21Xia1A22a2a5a7A23a8a3a4a6A24a9a11a10a12X1 A24 A24 A23 A23 A24 A22 A22 A22 A22 A22 A21 A21X2 A22 A22 A23 A23 A23 A23 A23 A23 A23 A23 A22 A223-эквивалентные состояния: П3={ A13, A23, A33, A43, A35};A31={a1, a2}= A21; A32={a5, a7}; A33={a8,}; A34={a3, a4, a6, a9, a11}= A23; A35={a10, a12}= A24.ak, AspA32A31XiA33A34A35a1a2a5a7a8a3a4a6a9a11a10a1233333333333A31X1 A5A5A2A2A4A3A3A3A3A3A1X2 A32 A32 A34 A34 A34 A34 A34 A34 A34 A34 A33 A33Совмещенная таблица минимизированного автомата МилиXiX1X2AkA1 A5A10 A3Y1 Y1A5 A3Y2 Y2A8A10Y1A3Y2A3A5Y2A3Y1A10A1Y2A8Y1Пример минимизации автомата Мили, заданного графом переходовРис.
1. До минимизацииXiX1X2a1 a2a4 a4Y1 Y1a1 a1Y1 Y1Рис. 2. После минимизацииaka3 a4 a5a1 a2 a2Y1 Y2 Y2a5 a3 a3Y2 Y1 Y1XiX1X2b1b3Y1b1Y1bkb2 b3b1 b1Y1 Y2b3 b2Y2 Y1Структурный синтез конечных автоматов.x{t}a(t)y{t}C1C2(Q1, Q2 ,..., Qn Q )Cn CАбстрактный автоматZ1Z2Zn ZСтруктурный автоматЭтапы структурного синтеза автоматов:1. Кодирование символов алфавитов абстрактного автомата.2. Получение кодированных таблиц переходов и выходов.3. Определение функций внешних переходов.4. Выбор типа элементарных автоматов.5. Получение функции возбуждения элементарных автоматов и функции выходов.6.
Построение принципиальной схемы автоматаВходной xj и выходной yi сигналы абстрактного автомата кодируются двоичными векторамидлины nC и nZ. x j ⇒ (c j1 , c j 2 , c j 3 … c jnc ); c jq ∈ {0;1}; j = 1, nx ;n c =]log 2 n x [y j ⇒ ( z j1 , z j 2 , z j 3 … z jnz ); z jl ∈ {0;1};j = 1, n y ,n z =] log 2 n y [Кодировка символов выходного алфавита: a k = (Qk1 , Qk 2 , Qk 3 … QknQ ); QkmQ ∈ {0;1}; k = 1, naгде n Q =] log 2 n a [ - количество элементарных автоматов.Структурная схема автоматаC1 C2CncКомбинационная схема формированияфункций возбуждения KCQ.P1ДляавтоматаМураQ1PnQP2Q2….Q nQКомбинационная схема формирования функций выхода KCZ.z1z2znzРис.
3Функция внешних переходов ϕi. определяет переход i-ого элементарного автомата в следующеесостояние: Q i ( t + 1) = ϕ i (Q1 , Q 2 ...Q i ,...Q n a , C1 , C 2 ...C n C ) t или Q( t + 1) = Φ (Q( t ), C( t )) .Сигналы возбуждения: P1 , P2 ,...PnQ непосредственно воздействуют на входы элементарныхавтоматов и формируются комбинационной схемой КСQPi (t ) = ψ i (Q(t ), C (t ))Выходные сигналы Z1, Z2, …Znz формируются комбинационной схемой КСZ функций выходов:Z l = γ l (Q (t ), C (t )), l = 1, nZ илиz( t ) = Γ(Q( t )) - для автомата Мура.
z( t ) = Γ(Q( t ), C( t )) - для автомата Мили.Кодирование сигналов и состояний автоматовКоличество способов кодирования n объектов k-разрядным двоичным кодом – числоPkn = 2k (2k − 1)… (2k − n + 1)размещений n элементов на k позициях:Пример кодирования автоматов Мура S1 и Мили S2, заданных на входном x={x1,x2,x3,x4} ивыходном y ={y1,y2,y3} алфавитах. Автомат S1 определён на алфавите состояний A1={a1,a2,a3,a4}, аавтомат S2 на алфавите A2={a1,a2,a3}.Определяем разрядность кодов символов:1. Алфавита состояний:Для S1: nQ=]log2na[=log24=2. Возможно na!=4!=24 способов кодирования.Для S2: nQ=]log2na[=]log23[=2.
Возможно P43 =4*3*2=24 способов кодирования.2. Входного алфавита: nC=]log2nX[=log24=2. Возможно nX!=4!=24 вариантов кодирования.3. Выходного алфавита: nZ=]log2nY[=]log23[=2. Возможно P43 =4*3*2=24 вариантов.x C1 C2x1 0 0x2 0 1x3 1 1x4 1 0Кодированиевходныхсимволовy z 1 z2y1 0 0y2 0 1y3 1 0КодированиевыходныхсимволовA Q1 Q2x1 0 0x2 1 0x3 0 1x4 1 1Кодированиесимволовсостоянийz1z 2C1 CQ 1 Q 2200000110001001110010101010010001000011000011001000000000C1CQ 1 Q 200210001000000110000100010000 0000000011100100001000001100-00-10-0000z 1z 2Рис. 5. Кодированная таблица автомата Мили.Рис.
4. Кодированная таблица автомата Мура.Преобразованные кодированные таблицы переходов и выходов.1)Автомат Мура.00z1 z 2C1CQ1Q 2 0020010C1CQ1 Q 2 00011021001Автомат Мили.00001011011010100100000011000000111000000000100100110010001000-1001-00-0000000000000100010011-000000100000Рис. 7Рис. 6Q1 ( t + 1)Q 2 ( t + 1)Q21111Q21111C21C2C1C1Q1Q1Рис. 8 Диаграммы Карно функций внешних переходов автомата Мура S1.Q 1 ( t + 1) = ( C1 C 2 + C 1C 2 Q1 Q 2 ) t ; Q 2 ( t + 1) = (C1 C 2 Q 1 Q 2 + C1 C 2 Q 1 Q 2 ) tQ1 ( t + 1)Q 2 ( t + 1)Q2111-Q21-C1-1-1-C2--C1Q1Рис. 9 Диаграммы Карно функций внешних переходов автомата Мили S2.Q 1 ( t + 1) = ( C1 C 2 ) t ; Q 2 ( t + 1) = (C 1 C 2 Q1 ) t-Q1C2.
