Минимизация конечных автоматов путем использования значений выходных переменных для кодирования внутренних состояний

Использование модели автомата класса D сокращает стоимость реализации в 1,33 раза. А модель автомата класса C, применяемая для большинства семейств ПЛИС, позволяет достигнуть наибольшего быстродействия конечного автомата. Выполнена верификация структурных моделей конечных автоматов, которая показала полную идентичность функционирования традиционных (классы A и B) и предложенных (классы C и D) структурных моделей. Приведено ориентированное на практическое использование в режиме ручного проектирования описание метода перехода от автомата типа Мили к автомату типа Мура (что обязательно при применении модели автоматов класса C) и метода кодирования внутренних состояний автоматов классов C и D.

Введение

Конечный автомат является математической моделью последовательностных схем, а, как известно [1], цифровые системы состоят из совокупности последовательностных и комбинационных схем. Кроме того, конечные автоматы широко используются в качестве контроллеров конкретных устройств, отдельных составных частей, а также общего устройства управления всей цифровой системы. Обычно при создании нового сложного проекта инженеру приходится всякий раз заново разрабатывать оригинальные конечные автоматы. Очевидно, что качество конечных автоматов, входящих в состав цифровой системы, во многом определяет успех всего проекта. Поэтому вопросы минимизации конечных автоматов всегда актуальны.

В роли критериев оптимизации конечных автоматов обычно выступают стоимость реализации, быстродействие и энергопотребление. В настоящее время для построения цифровых систем широко используются программируемые логические интегральные схемы (ПЛИС), поэтому многие методы оптимизации конечных автоматов ориентированы на реализацию конечных автоматов на ПЛИС.

Есть много различных подходов к оптимизации конечных автоматов, главным из которых считается минимизация внутренних состояний. Для этого разработано достаточно большое количество как точных [2, 3], так и приближенных методов [4, 5], пригодных для практического использования [6–8]. Вторым основным направлением оптимизации конечных автоматов являются способы кодирования внутренних состояний. На сегодня создано много методов кодирования внутренних состояний для различных целей оптимизации, в частности уменьшение стоимости реализации [1, 9], повышение быстродействия [1, 9, 10], снижение энергопотребления [11-13].

Кроме того, в [14] предлагается комплексный метод минимизации конечных автоматов, позволяющий еще на этапе минимизации внутренних состояний учитывать параметры элементной базы и используемый при синтезе метод кодирования внутренних состояний, а также оптимизировать такие параметры, как стоимость реализации, быстродействие и энергопотребление.

В настоящей работе для минимизации конечных автоматов предлагается использовать значения формируемых выходных наборов (выходных векторов) в качестве кода (или части кода) внутренних состояний. Данный подход непосредственно связан со структурными моделями конечных автоматов. Использование значений выходных переменных в качестве кодов внутренних состояний для автоматов типа Мура известно достаточно давно [15, 16], такие автоматы называют автоматами класса C [17]. Однако применение подобного подхода в отношении автоматов Мили стало возможным только после разработки структурной модели автомата класса D [18].

В данной работе представлены структурные модели конечных автоматов, которые позволяют использовать выходные векторы как коды внутренних состояний и для автоматов типа Мура, и для автоматов типа Мили. Показаны способы реализации автоматов классов C и D на языке Verilog, причем способ описания на языке Verilog автоматов класса D дан впервые, исследована эффективность предлагаемого подхода и верификация различных структурных моделей конечных автоматов. Кроме того, на простых примерах, без излишних математических строгостей, описывается метод [19] перехода от автомата типа Мили к автомату типа Мура, а также метод [9] кодирования внутренних состояний автоматов классов C и D. Предлагаемые методы ориентированы на практическое использование в режиме ручного проектирования. В заключение описаны возможные направления дальнейших исследований в этой области.

Структурные модели конечных автоматов

На практике наибольшее распространение получили две структурные модели конечных автоматов: автомат типа Мили (рис. 1а) и автомат типа Мура (рис. 1б).

Рис. 1. Структурные модели конечных автоматов:
а) автомат класса A;
б) автомат класса B;
в) автомат класса C;
г) автомат класса D

Поведение автомата типа Мили описывается с помощью следующих уравнений:

где φ — функция переходов; ψ — функция выходов; ζ_t — набор значений входных переменных (входной вектор) в момент автоматного времени t(t = 1, 2, 3, …); w_t — набор значений выходных переменных (выходной вектор), формируемый в момент автоматного времени t, a_t — настоящее состояние автомата; a_t+1 — следующее состояние автомата.

Поведение автомата типа Мура описывается следующими уравнениями:

Отличительной чертой автомата Мили является то, что выходной вектор w_t зависит как от входного вектора ζ_t, так и от внутреннего состояния a_t, а в автомате Мура выходной вектор w_t зависит только от внутреннего состояния а. На рис. 1а, б приведены структурные модели автоматов Мили и Мура, где комбинационная схема CL_ф реализует функцию переходов, комбинационная схема CL_ψ реализует функцию выходов, а регистр RG, управляемый сигналом синхронизации CLK, реализует память конечного автомата.

В практике инженерного проектирования часто встречаются конечные автоматы, когда на переходах в одни и те же состояния формируются одинаковые выходные векторы. Поэтому в [18] были предложены структурные модели конечных автоматов, которые позволяют в качестве кодов внутренних состояний использовать наборы значений выходных переменных.

Если каждый выходной вектор w_t автомата Мура совпадает с кодом его внутреннего состояния a_t, то поведение автомата можно описать следующим образом:

Данный тип автомата называют автоматом класса C [17], аналогично автоматы Мили и Мура — автоматами классов A и B соответственно. Структура автомата класса C показана на рис. 1в. Ее особенность заключается в отсутствии комбинационной схемы CL_ψ, а также в том, что все выходы автомата являются регистровыми, поскольку формируются на выходах регистра RG.

Если каждый выходной вектор w_t автомата Мили совпадает с кодом его следующего состояния a_t+1, то имеем автомат класса D (рис. 1г), поведение которого описывается следующими уравнениями:

К особенностям структуры автомата класса D следует отнести и отсутствие комбинационной схемы CL_ψ, однако выходы автомата являются комбинационными, поскольку формируются на выходах комбинационной схемы CL_Ф. Различие между автоматами классов C и D заключается в том, что в автомате класса C выходной вектор w_t совпадает с кодом настоящего состояния автомата a_t, а в автомате класса D выходной вектор w_t определяет код следующего состояния a_t+1.

Реализация конечных автоматов классов A, B, C и D с использованием языка Verilog

Рассмотрим реализацию конечных автоматов классов A, B, C и D на ПЛИС путем описания их функционирования на языке Verilog [20]. Пусть необходимо реализовать на ПЛИС конечный автомат, граф которого показан на рис. 2. Вершины графа (s0, s1, s2, s3 и s4) представляют внутренние состояния конечного автомата, а дуги между вершинами — его переходы. Возле каждой дуги записывается значение входного вектора, инициирующего данный переход, а через слеш («/») указывается значение выходного вектора, который формируется на данном переходе. В нашем примере конечный автомат имеет пять состояний, одну входную переменную и три выходные переменные. Отметим, что в общем случае как входные, так и выходные векторы конечного автомата являются троичными векторами, то есть каждый разряд может иметь значение «0», «1» или «-», где знак дефиса «-» обозначает неопределенное значение. Входной вектор, состоящий из одних дефисов, соответствует безусловному переходу (в нашем примере это переходы из состояний s2 и s3).

Рис. 2. Граф конечного автомата Мили

Описание конечного автомата класса A (Мили) на языке Verilog (листинг 1) имеет три входных порта (clk — для сигнала синхронизации, reset — для сигнала сброса, in — для значения входной переменной) и один выходной порт out шириной на три бита для значений выходных переменных. Поскольку конечный автомат имеет пять состояний, то для их кодирования достаточно трех разрядов бинарного кода. Настоящее состояние конечного автомата определяется с помощью переменной state, а следующее — next. Коды внутренних состояний описываются с помощью конструкции localparam.

module FSM_A (input clk, reset, // синхросигнал и сигнал сброса
in, // входная переменная
output reg [2:0] out); // три выходные переменные
reg [2:0] state, next; // настоящее и следующее состояние
localparam [2:0] s0=3’b000, // коды состояний
s1=3’b001,
s2=3’b010,
s3=3’b011,
s4=3’b100;
always @(*) // первый процесс
case (state)
s0: if (in) begin next=s1; out=3’b001; end
else begin next=s2; out=3’b010; end
s1: if (in) begin next=s3; out=3’b100; end
else begin next=s2; out=3’b010; end
s2: begin next=s3; out=3’b100; end
s3: begin next=s4; out=3’b011; end
s4: if (in) begin next=s1; out=3’b001; end
else begin next=s0; out=3’b000; end
endcase
always @ (posedge clk) // второй процесс
if (!reset) state <= s0;
else state <= next;
endmodule

Листинг 1. Описание автомата Мили (класса A) на языке Verilog

Поведение конечного автомата описывается с помощью двух процессов, определяемых процедурными операторами always. В первом процессе описывается комбинационная часть конечного автомата, а во втором — память конечного автомата. Здесь использован традиционный стиль описания конечных автоматов, когда нахождение автомата в некотором состоянии проверяется с помощью оператора выбора case, а проверка условий переходов из каждого состояния описывается с помощью условного оператора if. Для описания действий, выполняемых по определенному условию, предусмотрены операторные скобки (блок) begin…end, внутри которых определяется следующее состояние и выходной вектор, формируемый на данном переходе. Второй процесс описывает поведение памяти конечного автомата. На возрастающем фронте синхросигнала (конструкция posedge clk) при низком уровне на входе reset выполняется синхронный сброс автомата в начальное состояние s0, в противном случае автомат переходит в следующее состояние.

Автомат класса B, соответствующий нашему примеру, показан на рис. 3, а его описание приведено в листинге 2 (переход от автомата Мили к автомату Мура рассмотрен ниже). Отметим, что в графе автомата на рис. 3 выходные векторы записываются не на переходах, а рядом с состояниями, в которых они формируются. При описании поведения автомата класса B на языке Verilog (листинг 2) в каждом состоянии вначале определяется значение выходного вектора, формируемого в данном состоянии, а затем проверяются условия переходов в другие состояния.

Рис. 3. Граф конечного автомата Мура, соответствующий автомату на рис. 2

module FSM_B (input clk, reset, // синхросигнал и сигнал сброса
in, // входная переменная
output reg [2:0] out); // три выходные переменные
reg [2:0] state, next; // действительное и следующее
// состояние
localparam [2:0] s0=3’b000, // коды состояний
s1=3’b001,
s2=3’b010,
s3=3’b011,
s4=3’b100;
always @(*) // первый процесс
case (state)
s0: begin out=3’b000;
if (in) next=s1;
else next=s2;
end
s1: begin out=3’b001;
if (in) next=s3;
else next=s2;
end
s2: begin out=3’b010; next=s3; end
s3: begin out=3’b100; next=s4; end
s4: begin out=3’b011;
if (in) next=s1;
else next=s0;
end
endcase
always @ (posedge clk) // второй процесс
if (!reset) state <= s0;
else state <= next;
endmodule

Листинг 2. Описание автомата Мура (класса B) на языке Verilog

Выходной вектор автомата класса B может использоваться в качестве кода внутреннего состояния, если он однозначно определяет данное состояние, то есть выходной вектор должен быть ортогонален всем выходным векторам, формируемым в других состояниях автомата. Если это условие выполняется для каждого внутреннего состояния конечного автомата, такой конечный автомат относится к классу C (рис. 1в). Два выходных вектора являются ортогональными, если они по крайней мере в одном разряде имеют различные значащие (0 или 1) значения. Например, векторы «0-1» и «11-» ортогональны, а векторы «0-1» и «01-» не являются ортогональными.

Конечный автомат на рис. 3 удовлетворяет условиям возможности построения автомата класса C, при этом внутренние состояния имеют следующие коды: s0 — «000», s1 — «001», s2 — «010», s3 — «100», s4 — «011». Описание автомата класса C на языке Verilog приведено в листинге 3. Здесь в первом процессе описываются только переходы между состояниями, а значения выходов автомата определяются с помощью отдельного оператора непрерывного назначения assign.

module FSM_C (input clk, reset, // синхросигнал и сигнал сброса
in, // входная переменная
output [2:0] out); // три выходные переменные
reg [2:0] state, next; // действительное и следующее
// состояние
localparam [2:0] s0=3’b000, // коды состояний
s1=3’b001,
s2=3’b010,
s3=3’b100,
s4=3’b011;
always @(*) // первый процесс
(* full_case, parallel_case *)
casex (state)
s0: if (in) next=s1;
else next=s2;
s1: if (in) next=s3;
else next=s2;
s2: next=s3;
s3: next=s4;
s4: if (in) next=s1;
else next=s0;
endcase
always @(posedge clk) // второй процесс
if (!reset) state <= s0;
else state <= next;
assign out=state; // определение значений выходов
endmodule

Листинг 3. Описание автомата класса C на языке Verilog

Аналогично, выходной вектор автомата Мили может использоваться в качестве кода внутреннего состояния, если он формируется на всех переходах в некоторое состояние и однозначно определяет данное состояние, то есть не формируется на переходах в другие состояния. Если эти условия выполняются для каждого внутреннего состояния конечного автомата, то такой конечный автомат принадлежит к классу D (рис. 1г). Конечный автомат на рис. 2 удовлетворяет условиям возможности построения автомата класса D, при этом внутренние состояния имеют те же коды: s0 — «000», s1 — «001», s2 — «010», s3 — «100», s4 — «011». Описание автомата класса D на языке Verilog приведено в листинге 4.

module FSM_D (input clk, reset, // синхросигнал и сигнал сброса
in, // входная переменная
output [2:0] out); // три выходные переменные
reg [2:0] state, next; // действительное и следующее
// состояние
localparam [2:0] s0=3’b000, // коды состояний
s1=3’b001,
s2=3’b010,
s3=3’b100,
s4=3’b011;
always @(*) // первый процесс
(* full_case, parallel_case *)
casex (state)
s0: if (in) next=s1;
else next=s2;
s1: if (in) next=s3;
else next=s2;
s2: next=s3;
s3: next=s4;
s4: if (in) next=s1;
else next=s0;
endcase
always @(posedge clk) // второй процесс
if (!reset) state <= s0;
else state <= next;
assign out=next; // определение значений выходов
endmodule

Листинг 4. Описание автомата класса D на языке Verilog

Отличие описаний в листингах 3 и 4 заключается только в том, что значения выходов для автомата класса C определяются переменной state, а значения выходов для автомата класса D определяются переменной next.

Исследование эффективности использования моделей конечных автоматов классов A, B, C и D

Экспериментальные исследования эффективности структурных моделей конечных автоматов классов A, B, C и D (рис. 1) выполнялись с помощью САПР Quartus II версии 13.0 для ПЛИС фирмы Altera семейств MAX II, MAX V, MAX 3000A, Cyclone III, Cyclone IV GX и Arria II GX. В качестве критерия оптимизации выполняемой САПР Quartus II был выбран Balanced, остальные параметры логического синтеза были приняты по умолчанию. Результаты экспериментальных исследований приведены в таблице 1.

Анализ таблицы 1 показывает, что применение модели автомата класса C в 2 раза уменьшает стоимость реализации по сравнению с автоматом класса A для ПЛИС всех семейств, а по сравнению с автоматом класса A для семейства Arria II GX в случае кодирования Auto — даже в 2,67 раза. Использование модели автомата класса D позволяет в 1,33 раза уменьшить стоимость реализации по сравнению с автоматом класса A для ПЛИС семейств MAX II, MAX V, Cyclone III и Cyclone IV GX. Для семейств MAX 3000A и Arria II GX стоимость реализации модели автомата класса D совпала со стоимостью реализации автомата класса A.

Кроме того, использование модели автомата класса C в случае способа кодирования Auto позволило достигнуть наибольшего быстродействия для семейств MAX II, MAX V, Cyclone III и Cyclone IV GX. Для семейства MAX 3000A быстродействие постоянно для всех моделей конечных автоматов. Для семейства Arria II GX максимальное быстродействие достигается в модели автомата класса B при использовании способа кодирования Auto.

Верификация конечных автоматов классов A, B, C и D

Проверка функционирования (функциональное моделирование), а также верификация поведения конечных автоматов классов A, B, C и D во времени (временное моделирование) выполнялись средствами САПР Quartus II. Проведенные исследования показали, что функционирование автоматов классов A и D, а также B и C полностью совпадает. Временные диаграммы автоматов классов A и D для нашего примера показаны на рис. 4, а автоматов классов B и C — на рис. 5.

Рис. 4. Временные диаграммы функционирования автоматов классов A и D

Рис. 5. Временные диаграммы функционирования автоматов классов B и C

Следует отметить, что автомат типа Мура (классы B и C) по сравнению с автоматом типа Мили (классы A и D) функционирует с запаздыванием на один такт в начале работы (после включения питания), а также в случае сброса. Данный факт следует учитывать при принятии решения о переходе от автомата типа Мили к автомату типа Мура, поскольку для некоторых проектов такое запаздывание может быть недопустимым.

Переход от автомата типа Мили к автомату типа Мура

Проведенные экспериментальные исследования показали высокую эффективность модели автомата класса C по сравнению с автоматами классов A, B и D — как по стоимости реализации, так и по быстродействию. Однако для использования модели автомата класса C конечный автомат должен быть автоматом типа Мура. Известно много способов перехода от автомата типа Мили к автомату типа Мура, одним из которых является метод [19], основанный на операции расщепления внутренних состояний. Отметим, что операция расщепления внутренних состояний относится к операциям эквивалентного преобразования конечного автомата и не изменяет алгоритм его функционирования.

Метод [19] перехода от автомата типа Мили к автомату типа Мура рассмотрим на примере конечного автомата, граф которого показан на рис. 6.

Конечный автомат может быть преобразован в автомат типа Мура, если для каждого внутреннего состояния автомата выполняется условие, что на всех переходах в данное состояние формируются одинаковые выходные векторы. Суть предлагаемого подхода заключается в следующем: если в некоторое состояние ведут несколько переходов, на которых формируются разные выходные векторы, то состояние расщепляется на несколько состояний таким образом, чтобы на переходах в каждое вновь образованное состояние формировались одинаковые выходные векторы.

В нашем примере (рис. 6) условие для состояний автомата типа Мура нарушено для состояния s1. В состояние s1 ведут два перехода: из состояния s0, на котором формируется выходной вектор «001», и из состояния s4, на котором формируется выходной вектор «100». Поскольку в состояние s1 ведут переходы, где формируются два различных выходных вектора, то состояние s1 расщепляется на два состояния — s1_1 и s1_2 (рис. 7).

Рис. 6. Граф конечного автомата типа Мили

Теперь условие для состояний автомата типа Мура выполняется для всех внутренних состояний, и автомат может быть приведен к автомату типа Мура. Для этого выходные векторы, формируемые на переходах в некоторое состояние, записываются непосредственно возле этого состояния (рис. 7). Последнее означает, что выходные векторы непосредственно не зависят от входных переменных, а только от нахождения автомата в определенном состоянии.

Рис. 7. Граф конечного автомата типа Мура, полученный из автомата Мили на рис. 6 путем расщепления внутреннего состояния s1 на два состояния — s1_1 и s1_2

Кодирование внутренних состояний автоматов классов C и D

Главная цель кодирования внутренних состояний при синтезе автоматов классов C и D заключается в обеспечении взаимной ортогональности всех кодов внутренних состояний конечного автомата. Дело в том, что в различных состояниях автомата (при синтезе автомата класса C) или на переходах в различные состояния (при синтезе автомата класса D) могут формироваться неортогональные выходные векторы. Если такое случается, необходимо вводить дополнительные разряды кода для обеспечения взаимной ортогональности кодов внутренних состояний [9].

Рассмотрим кодирование внутренних состояний при синтезе автомата класса C для автомата Мура на рис. 7. Для этого строится троичная матрица W, строки которой соответствуют внутренним состояниям, а столбцы — выходным переменным конечного автомата. Строки матрицы W заполняются значениями выходных векторов, которые формируются в соответствующих состояниях (табл. 2, столбцы e₃, e₂ и e₁).

Отметим, что в общем случае матрица W является троичной, а не булевой, поскольку выходные векторы в отдельных разрядах могут иметь неопределенные значения. Дополнительные столбцы матрицы W соответствуют дополнительным переменным обратной связи, вводимым для обеспечения взаимной ортогональности кодов состояний. Теперь задача заключается во введении минимального числа дополнительных разрядов кода (дополнительных столбцов матрицы W) и кодировании строк матрицы М дополнительными разрядами кода (определения значений дополнительных столбцов матрицы W) таким образом, чтобы все строки матрицы W были взаимно ортогональны. В последующем строки матрицы W будут определять коды внутренних состояний автомата класса C.

В нашем примере (табл. 2, столбцы e₃, e₂ и e₁) все коды внутренних состояний взаимно ортогональные, за исключением состояний s1_2 и s3. Поэтому для их различия вводится дополнительный разряд кода, которому соответствует переменная e₀, причем состояние s1_2 в разряде e₀ кодируется значением «1», а состояние s3 — значением «0». Значения в остальных строках столбца e₀ не влияют на решение задачи и для определенности могут быть обнулены. Более строгая постановка задачи кодирования внутренних состояний автомата класса C и методы ее решения приводятся в [9]. В качестве кодов внутренних состояний автомата класса C принимаются значения соответствующих строк матрицы W. Описание автомата класса C на языке Verilog для нашего примера приведено в листинге 5.

module FSM_C_2 (input clk, reset, // синхросигнал и сигнал сброса
in, // входная переменная
output [2:0] out); // три выходные переменные
reg [3:0] state, next; // настоящее и следующее
// состояние
localparam [3:0] s0=4’b000_0, // коды состояний
s1_1=4’b001_0,
s1_2=4’b100_1,
s2=4’b010_0,
s3=4’b100_0,a s4=4’b011_0;
always @(*) // первый процесс
(* full_case, parallel_case *)
casex (state)
s0: if (in) next=s1_1;
else next=s2;
s1_1: if (in) next=s3;
else next=s2;
s1_2: if (in) next=s3;
else next=s2;
s2: next=s3;
s3: next=s4;
s4: if (in) next=s1_2;
else next=s0;
endcase
always @ (posedge clk) // второй процесс
if (!reset) state <= s0;
else state <= next;
assign out=state[3:1]; // определение значений выходов endmodule

Листинг 5. Описание автомата класса C на языке Verilog для автомата на рис. 7

Внутренние состояния автомата класса D кодируются аналогичным образом. Строится троичная матрица W, чьи строки соответствуют внутренним состояниям, а столбцы — выходным переменным конечного автомата. Строки матрицы W заполняются значениями выходных векторов, которые формируются на переходах в соответствующие состояния. Ортогонализация строк матрицы W выполняется точно так же, как для автомата класса C. В качестве кодов внутренних состояний принимаются значения строк матрицы W. В нашем примере матрица W для кодирования внутренних состояний автомата класса D совпадает с матрицей W для автомата класса C (табл. 2). Описание автомата класса D на языке Verilog для конечного автомата на рис. 7 приведено в листинге 6.

module FSM_D_2 (input clk, reset, // синхросигнал и сигнал сброса
in, // входная переменная
output [2:0] out); // три выходные переменные
reg [3:0] state, next; // настоящее и следующее
// состояние
localparam [3:0] s0=4’b000_0, // коды состояний
s1_1=4’b001_0,
s1_2=4’b100_1,
s2=4’b010_0,
s3=4’b100_0,
s4=4’b011_0;
always @(*) // первый процесс
(* full_case, parallel_case *)
casex (state)
s0: if (in) next=s1_1;
else next=s2;
s1_1: if (in) next=s3;
else next=s2;
s1_2: if (in) next=s3;
else next=s2;
s2: next=s3;
s3: next=s4;
s4: if (in) next=s1_2;
else next=s0;
endcase
always @ (posedge clk) // второй процесс
if (!reset) state <= s0;
else state <= next;
assign out=next[3:1]; // определение значений выходов endmodule

Листинг 6. Описание автомата класса D на языке Verilog для автомата на рис. 7

Отметим, что все рассмотренные в данной работе методы реализованы в пакете ZUBR [21] и при необходимости могут быть использованы в автоматическом режиме.

Заключение

Проведенные экспериментальные исследования показали высокую эффективность структурной модели автомата класса C при реализации конечных автоматов на ПЛИС, как по стоимости реализации, так и по быстродействию. Однако для применения модели автомата класса C конечный автомат должен быть преобразован в автомат типа Мура, который функционирует с запаздыванием на один такт в начале работы и в случае сброса в начальное состояние. Это обстоятельство следует учитывать при использовании модели автомата класса C. Модель автомата класса D также достаточно эффективна и в отличие от модели автомата класса C может быть применена к любому конечному автомату.

В представленной работе для кодирования внутренних состояний были использованы значения выходных переменных конечного автомата, но с этой же целью можно использовать и значения входных переменных. Поэтому перспективным видится исследование возможности использования значений входных переменных в качестве кодов внутренних состояний конечных автоматов, а также совмещение обоих методов.

Работа выполнена при частичной финансовой поддержке Белостокского технического университета (Польша), грант S/WI/1/2013.