ПРЕДСТАВЛЕНИЕ АВТОМАТА ТАБЛИЦЕЙ ПЕРЕХОДОВ
Существуют различные способы представления конечного автомата. Мы рассмотрим один из них ■— представление функций переходов и выходов автомата с помощью таблиц переходов и выходов.
Использование таблиц переходов и выходов оказывается удобным средством представления автоматов как при синтезе, так и пои анализе их (Ьѵнкииониоования.
делена не для всех пар значений р и %, поэтому данная таблица переходов представляет частичный автомат.
Таблица 2.1
Рі
92
рз
Р4
| Хі | (хі) | X2 | ■ Х4 ' ' | |
| Х2 | Хі | (x2) | Хз | — |
| Хз | — | — | (%з) | Х4 |
| Х4 | Хі | — | Х5 | (Уц) |
| Х5 | — | 'x6 | (хб) | х4 |
| Хб | Хі | (Хб) | ___ | — |
Таблица 2.2
| Внут реннее состояние | Состояния входа | |||
| Рі | Р2 | Рз | Р4 | |
| ІН | (1) | 2 | 4 | |
| 2 | 1 | (2) | 3 | — |
| 3 | — | (3) | 4 | |
| 4 | 1 | — | 5 | (4) |
| 5 | — | 6 | (5) | 4 |
| 6 | 1 | (6) | :— | |
| Т а б л и ц а 2.3 | ||||
| Внут | Состояния входа | |||
| реннее | ||||
| состояние | Рі | Р2 | bgcolor=white>РзР4 | |
| 1н | (1) | 2 | 4 | |
| 2 | 1 | (2) | 3 | — |
| 3 | — | (3) | 4 | |
| 4 | 1 | — | 5 | (4) |
| 5 | 2 | 6 | (5) | 4 |
| 6 | 1 | (6) | — | |
Внутреннее состояние автомата Kj назовем устойчивым при состоянии входа р*, если (p(Xj, р i)=Xj.
Внутреннее состояние автомата Xj назовем неустойчивым при состоянии входа рі, если cp(xj, рі)фх^. Например, в табл. 2.1 указано: ср(%і,рі) —%и следовательно, внутреннее состояние Х\ устойчиво при состоянии входа рг, ф(хь Р2) =К2¥=кі, значит, внутреннее состояние Хі неустойчиво при состоянии входа р2; Ф (х2> Р2) — х2, следовательно,внутреннее состояние х2 устойчиво при состоянии входа р2. Все внутренние состояния, устойчивые при соответствующем состоянии входа, отмечаются в таблице переходов символом X, взятым в круглые скобки. Для простоты условимся указывать в таблице переходов вместо Xj номер / (см. табл. 2.2, где приведена та же таблица переходов, что и в табл. 2.1). В этой таблице через 1н обозначено начальное внутреннее состояние автомата.
Важный класс составляют автоматы, которые представляются нормальной таблицей переходов. В таких автоматах заданы переходы только во внутренние состояния, устойчивые при соответствующем состоянии входа. Более строго говоря, таблица переходов автомата является нормальной таблицей переходов, если ДЛЯ любого ПОЛНОГО СОСТОЯНИЯ \кц, на котором функция ф (Xj, рг) определена, имеет место
ф(ф(^і. Рг), Рг) =q)(Xj, Рі) .
Так, в табл. 2.2. представлена нормальная таблица переходов. Если же в ней вместо прочерка указать значение функции
первоначальной таблицей переходов. Например, в табл. 2.4 и 2.5 представлены первоначальные таблицы переходов.
Первоначальная таблица переходов является исходной формой представления автомата. В процессе составления этой таблицы выясняется число внутренних состояний автомата (это число может быть избыточным), задаются функции переходов и выходов, определяющие закон функционирования автомата. Составлению первоначальной таблицы переходов предшествует формулировка задания на проектирование автомата. В ходе построения таблицы выясняются непротиворечивость и полнота задания закона функционирования автомата.
Табличная форма записи функций переходов и выходов компактна и удобна для заключительного этапа абстрактного синтеза и для последующего структурного синтеза автомата.Однако при задании автомата по словесному описанию его работы, особенно в случае проектирования сложных автоматов, табличная форма представляется не столь естественной и наглядной, как, например, графический способ задания автомата. В инженерной практике часто пользуются графическими методами описания функционирования проектируемых устройств, наглядно отображающими последовательности поступления входных сигналов на автомат и порождаемые ими последовательности выходных сигналов. Поэтому представляется целесообразным записывать эти последовательности в стандартной графической форме, а затем переходить к первоначальной таблице переходов автомата. с
Укажем на естественный переход от первоначальной таблицы переходов автомата к соответствующему ей ориентированному
При логическом проектировании нередко приходится работать с частичными графами автомата. Дело в том, что специалист, приступающий к проектированию дискретного устройства автоматики, обычно имеет (допустим, исходя из технического задания на проектирование) информацию о том, сколько внешних входов и выходов должен содержать автомат, какие входные и выходные.наборы двоичных сигналов сопоставлены возможным состояниям входа и выхода автомата, в какой последовательности возможно поступление двоичных сигналов на входы автомата и т. д. Он знает, как должно взаимодействовать проектируемое устройство с другими устройствами или блоками создаваемой системы автоматики в целом. При этом известно, что некоторые последовательности состояний входа и выхода автомата могут быть запрещены.
При построении графа автомата необходимо выполнить два требования: 1) в графе автомата должны быть представлены своими вершинами все возможные по условиям работы автомата пары (р, Я) и указаны все возможные по условиям работы дуги между этими вершинами (требование полноты); 2) из любой вершины графа автомата запрещены дуги в две и более вершин, представляющих одинаковые состояния входа (требование непротиворечивости).
Подробно с методом построения графа автомата можно ознакомиться в работах [35, 361.
стью смены сообщении, отраженной на временной диаграмме, приведенной на рис. 2.3,а. В результате такого построения получим граф, изображенный на рис. 2.4.
Проверим, удовлетворяет ли построенный граф двум требованиям к графу автомата, сформулированным выше. Сначала выясним, представлены ли на графе все возможные сообщения о работе формирователя. На входе формирователя возможны
На примере формирователя сигналов будет иллюстрироваться и дальнейшая последовательность логического проектирования.
2.3.