Спирина, М.С. Дискретная математика

q(t) = 5(q(t - 1), *(/)), где x(t) e X, ■y(t) = X (q ( t- l) , x ( t ) ) ,r a c y ( t ) e Y , .0(0) = q0, где q(t) e Q. Табличный способ. Функцию перехода 5 и выхода X можно пред­ ставить в виде таблицы, столбцы которой соответствуют входным символам (элементы входного алфавита X), а строки — состояни­ ям (элементы конечного множества Q). Поэтому пересечение /-й строки и у - го столбца — клетка (/, j ) — соответствует аргументу функций 5 и Я автомата в момент, когда он находится в состоя­ нии qh на его входе — слово хр а в самой соответствующей клетке запишем значения функций 8 и Я. Таким образом, вся таблица соответствует множеству Q х X. Для автомата Мили она имеет вид табл. 7.1. Т а б л и ц а 7.1 Таблица переходов автомата Мили *1 Х 2 х* 01 5(01, xOlMtfi, х,) 5(0 i , x 2 )|X(? i , x ,) 5(01,х*)|Ц?ь х*) Яг 5 ( 02 , х 1 )|Х( 0 1, х,) 5 ( 02 , х 2 )|Я.(?ь х,) 5(02, X*) 1Х( 02 , X*) ... . .. Яп 5(0„, х,)|Я(?„, х,) 5(0„, х2) | X(q„, х2) . .. 5(0„, хк) |Я(< 7 „, хк) В этой таблице 8 : Q х X -> Q, X: Q х X -> Y. В таблице переходов для автомата Мура каждая строка опреде­ ляет состояние < 7 , и выходной сигнал у} = X(q,), соответствующий этому состоянию (табл. 7.2). Т а б л и ц а 7.2 Таблица переходов автомата Мура Х| х 2 ... Х( 0 ) 01 5(0ь х,) 5 ( 0 ь х2) ... 8 ( 0 i, хт) У \ Яг 5(02, х,) 5 ( 02 , х2) 5 ( 02 , хт) Уг ... ... Яп 5(0„, х,) 5(0Л, х2) 5( 0 „, хт) У п В этой таблице 8 : Q х X -> Q, X: Q -» Y При заполнении таблицы переходов каждая клеточка однознач­ но определяется парой символов: символом следующего состоя­ ния и символом выходного сигнала. Таким образом, рассматрива­ 348