Конечные автоматы ч.1

Конечные автоматыАбстрактный автомат задаётся множеством из 6 элементов: S={X, Y, A, f, g, a(0)}, где:X={x1, x2,…, xnX } – множество входных сигналов (входной алфавит);Y={y1, y2,…, ynY } – множество выходных сигналов (выходной алфавит);А={a1,a2,…, anA } – множество состояний (алфавит состояний);f – функция переходов автомата;g – функция выходов автомата;(0)a – начальное состояние автомата.Законы функционирования автоматов Мили и Мура:Автомат Милиа(t+1) = f(a(t), x(t)); t = 0, 1, 2,…y(t)=g(a(t), x(t))Автомат Мураа(t+1) = f(a(t), x(t)); t = 0, 1, 2,…y(t) = g(a(t))xj yiamxjamaSyiaSРис. 1. Граф автомата Мили.ykyixjamилиaSamxjaSykyiРис. 2. Граф автомата Мура.Графы эквивалентных автоматов Мура S1 (рис.3)и Мили S2 (рис.4), определённых наалфавитах x = {x1,x2,x3,x4} и y = {y1,y2,y3}. Эти автоматы на любую входную последовательность,оканчивающуюся на x1x2, формируют выходной сигнал y2, а на x1x2x3 сигнал y3, то есть,распознают последовательности x1x2 или x1x2x3x4+x3x2+x3+x4y1y1x1x1a1x2+x4a2y3x1x2a4x3x 2 + x3 + x4y1a1x1x1+x3+x4x3 + x4y1x 2 + x4 x3+y1y3a3y2Рис.

3. Граф переходов и выходов автомата Мура S1.x1y1x1y1a2x2y2x1y1a3Рис. 4. Граф переходов и выходов автомата Мили S2.Задание автомата в виде таблиц переходов и выходовy(t)y1y1y2y3a1a2a3a4x1a2a2a2a2x2a1a3a1a1x(t)a(t)x3a1a1a4a1x4a1a1a1a1Таблицавыходовx(t)Таблицапереходовa(t)a1x1a2x2a1x3a1x4a1a2y1y1y1y1a2a3a1a1a3a2y1a1y2a1y1a1y1y1y1y3y1Рис. 6. Таблица переходов ивыходов автомата Мили S2.a(t+1)Рис. 5. Таблица переходов и выходов автомата Мура S1Задание автомата в виде матриц переходов и выходовy(t)y1y2y3y4a1a2a3a4a1x2+x3+x4x1--a2x3+x4x1x2-a3x2+x4x1-x3a4x2+x3+x4x4--a(t+1)a(t)Матрицавыходовa(t+1)a(t)МатрицапереходовРис. 7. Матрицы переходов и выходов автомата Мура S1.a1a1x 2 + x 3 + x1y1x1y1a2x3 + x4y1x1y1a3x3 + x 4 x3+y1y3x1y1a(t)a(t+1)Автомат Мили.a1a1a1a1a2a2a2a2a3a3a3a3a4a4a4a4a1a2a3a4a1a2a3a4a1a2a3a4a1a2a3a4xx2+x3+x4x1x3+x4x1x2x3+x4x1x3x1+x2+x4x1-a3x2y2-Рис.

8. Матрицы переходов и выходовавтомата Мили S2.Табличная форма представления матриц переходов и выходовАвтомат Мура.a2a(t)a(t+1)a1a1a1a2a2a2a3a3a3a1a2a3a1a2a3a1a2a3Рис. 9.x/yx2+x3+x4/y1x1/y1x3+x4/y1x1/y1x2/y2(x2+x4)/y1+x3/y3x1/y1-.