Задан конечный автомат (X,Q,Y,φ,ψ), где X – входной алфавит, Q – множество возможных состояний

Задан конечный автомат (X,Q,Y,φ,ψ), где X – входной алфавит, Q – множество возможных состояний автомата, Y – выходной алфавит, φ: X×Q→Q – функция переходов, ψ: X×Q→Y – функция выходов, с таблицей пар значений (φ(x,q),ψ(x,q)). X={0,1}, Q={0,1,2,3}, Y={0,1}. Таблица значений (φ(x,q), ψ(x,q)) x \ q 0 1 2 3 0 (1,1) (3,0) (2,0) (2,0) 1 (2,1) (2,0) (3,0) (3,0) 1. Построить диаграмму для данного автомата. 2. Преобразовать таблицу в двоичную форму (задать в виде таблицы значений булевых функций).

Для построения диаграммы (граф) автомата, рассмотрим заданную таблицу значений. Алфавит состояний Q={0,1,2,3}, следовательно, в графе будут четыре вершины, соответствующие каждому из состояний.
На первом месте в каждой клетке таблицы идет новое состояние φ(x,q) – т.е. то состояние, в которое перешел автомат. Старое (исходное) состояние q отражено в шапке таблицы.
Имеем такие переходы между состояниями:
Для столбца 0: 0=>1, 0=>2;
Для столбца 1: 1=>3, 1=>2;
Для столбца 2: 2=>2, 2=>3;
Для столбца 3: 3=>2, 3=>3.
Каждый из этих переходов изображается стрелкой на графе, идущей из старого состояния в новое:
Далее над каждой стрелкой нужно подписать входной и выходной сигнал, соответствующий данному переходу между состояниями . Входной сигнал x идёт в столбце слева, выходной ψ(x,q) стоит на втором месте в каждой клетке таблицы.
Построение двоичной таблицы.
Для перевода таблицы из условия задачи в двоичную форму, сначала определим число двоичных разрядов для входного сигнала, для состояний и для выходного сигнала

. Входной сигнал x идёт в столбце слева, выходной ψ(x,q) стоит на втором месте в каждой клетке таблицы.
Построение двоичной таблицы.
Для перевода таблицы из условия задачи в двоичную форму, сначала определим число двоичных разрядов для входного сигнала, для состояний и для выходного сигнала