Конечные автоматы ч.1 (561946)
Текст из файла
Конечные автоматыАбстрактный автомат задаётся множеством из 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-.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.