Граф - автомат
Cтраница 1
 |
Граф МПА. [1] |
Граф автомата для МПА с большим числом состояний теряет свою наглядность. В первом столбце такой таблицы записываем состояния am, во втором - а. Строка таблицы соответствует одному переходу из ат в ая для заданной ГСА. [2]
Граф автомата - это ориентированный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними. Для графа автомата Мили выходной сигнал tWgsW, формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной ат, отмеченной состоянием ат, в котором он формируется. Если переход в автомате из состояния ат в состояние as производится под действием нескольких входных сигналов, то дуге графа, направленной из ат в as, приписываются все эти входные и соответствующие выходные сигналы. [3]
 |
Граф-автомата Мили а2 и отмеченные сигналами x2 / yz и. [4] |
Граф автомата Мили определяется по отмеченному графу микропрограммы ( см. рис. 5.2) следующим образом. На рис. 5.3 проставляются вершины графа, соответствующие состояниям а, аъ а2, а3 автомата. [5]
Имея таблицу переходов или граф автомата и зафиксировав определенную нумерацию его состояний, легко построить квадратную автоматную матрицу этого автомата. [6]
Легко видеть, что граф автомата, благодаря введенным на нем ( в соответствии со сделанным выше описанием) обозначениям вершин и ребер, полностью задает автомат - при условии, что каким-то образом отмечена вершина графа, соответствующая начальному состоянию этого автомата. [7]
 |
Граф МПА. [8] |
В [2] изложен метод построения графа автомата и для МПА Мура. [9]
Указанным переходам соответствуют три ребра графа автомата, отмеченные сигналами хг / уг, хгх2 / у2, x xjtjz соответственно. Из точки at графа микропрограммы ведут два пути в точку аа. [10]
 |
Пример преобразования нечетной последовательности ветвей графа в четную. [11] |
При этом для любого узла графа автомата все входящие ветви должны быть отмечены одним из символов 77, Т2, а все выходящие ветви - другим. В свою очередь, такую разметку графа можно всегда выполнить, если только все замкнутые последовательности его ветвей содержат четное их число. [12]
В рассматриваемой нами ситуации, когда граф автомата G не имеет циклов ( кроме единичных, поскольку случай gyg не исключается), важную роль играет тот факт, что А не может возвращаться s вершины, которые он оставил. Другое важное обстоятельство состоит в том, что функция л может быть произвольной, в любой момент времени на вход автомата А может поступить любой символ х независимо от предыстории его движения. [13]
 |
Граф микропрограммы. [14] |
Для определения закона функционирования автомата Мура строится граф автомата или отмеченная таблица переходов. [15]
Страницы: 1 2 3 4