Формальные языки описания дискретного автомата

Способы описания дискретных автоматов.

 

 

Для описания работы дискретного автомата используются следующие языковые средства:

1. Таблицы переходов (функции δ);
2. Таблицы выходов(функции λ);
3. Графы переходов;
4. Граф - схемы алгоритмов;
5. Логические схемы алгоритмов.

 

Разновидности таблиц состояний дискретных автоматов.

 

Таблица переходов (функция δ)

Внутренне состояние дискретного автомата в конкретный момент времени описывается табличной функцией, смысловое содержание которой представлено в табл. 1.

Таблица 1

	а1	а2	а3	а4	Смысл этой таблицы состоит в том, что некоторый дискретный автомат последовательно за четыре такта получает на свой вход сигналы: Х1;Х2;Х3;Х4.
Х1	а1	а3	-	а1
Х2	-	а1	а1	а2
Х3	а4	-	а2	а3
Х4	-	-	-	а2

Этот дискретный автомат может произвольно принимать четыре возможных внутренних состояния: а1,а2,а3,а4. Согласно этой таблице при действии сигнала Х1 автомат из состояния а1 остается в этом же состоянии, но из состояния а2 переходит в состояние а3, а из состояния а4 возвращается в состояние а1. В этом такте состояние а3 автомата безразлично, т. к. из него возможен переход в любое другое состояние. Согласно этой таблице аналогично объясняются переходы состояний автомата в последующих тактах.

 

Таблица выходов (функция λ)

 

Таблицей выходов каждому внутреннему состоянию дискретного автомата на соответствующем такте задается величина выходного сигнала. В общем случае это описывается табличной функцией λ[a(t),x(t)], смысловое содержание которой представлено в табл. 2.

Таблица 2

	а1	а2	а3	а4	Смысл этой таблицы состоит в том, что за четыре входных такта Х1;Х2;Х3;Х4 дискретный автомат формирует конкретный входной сигнал при соответствующем
Х1	y1	y3	-	y4
Х2	-	y1	y1	y2
Х3	y4	-	y2	y3
Х4	-	-	-	y4

внутреннем его состоянии: а1,а2, а3,а4.

Согласно табл. 2 при действии сигнала Х1 на выходе автомата при его внутреннем состоянии а1 формируется сигнал y1, а в состоянии а4 этот автомат выдает сигнал y4. Состояние а3 в этом такте безразлично.

Для описания работы дискретного автомата с помощью графа строится обобщенная таблица переходов, в которой объединяется содержание двух предыдущих таблиц.

Таблица 3

	а1	а2	а3	а4	Таблица 3 иллюстрирует принцип этого объединения. Такая таблица является основой для построения графа переходов. Если в таблице 3 не все клетки заполнены
Х1	а1/y1	а3/y3	-	а1/y4
Х2	-	а1/y1	а1/y1	а2/y2
Х3	а4/y4	-	а2/y2	а3/y3
Х4	-	-	-	а2/y4

(определены), то такой автомат считается не полностью определенным или частичным.

Описание работы дискретных автоматов с помощью графов.