>) Несущественная переменная является такой переменной, которая оставляет без изменения значение функции независимо от значения, принимаемого этой переменной.

быть записано в форме

Zv - g(Xv-i, Xv-i....."-и v-y,. v-/2.....v-/J.

(6.1)

где принято, что О < 1 < 2 < • • • < <u и 1 < yl < Уг < •.. ... < Д. Если добавить ряд несущественных переменных i) и принять /„ = 1 и Уг, = М2 ™ урзвнение (6.1) можно записать в виде

Zv = /(Arv. Av-l.....-"fv-H,. Z-h Z„-2.....v J. (6.2)

Для того чтобы преобразовать приведенное характеристическое уравнение в характеристические стандартные функции Д и Д конечного автомата, переменную s определим так, чтобы Sy являлась упорядоченным набором значений

(lii + M2) переменных (aTv-i. Arv-2. -v-n,. Tv-i. Zv 2. ••• Zv-hj). Равенство (6.2) тогда примет вид

-2v = /z(v. *v)- (6-3)

Из определения s следует, что s+j определяется так:

(aTv. -fv-b •••• -"V-Hi+b v, v-l.....v-Hj+i) =

= (ATv. ATv-1.....-"v-Hi+b f {Xy, ATv-li АГу-ц,>

Zv-I, Zv 2. Tv-Hj), v 1.....Zv Hj+i). (6.4)

Следовательно,

*v+l = (Arv> .....-"v-n,. .....V-Hj) (6.5)

5v+l = A(v. *v)- (6-6)

Уравнения (6.3) и (6.6) могут рассматриваться как характеристические функции конечного автомата. Следовательно, множество упорядоченных наборов значений (мх + Мг) переменных (aTv-i, лгу 2.....-"v-n,. Zv-i. Zv-2.....Zv-ii) адекватно множеству состояний системы, представленной урав-

6.2] ПРЕДСТАВЛЕНИЕ СИСТЕМ С КОНЕЧНОЙ ПАМЯТЬЮ 213

нением (6.2). Если число символов входного и выходного алфавитов для системы соответственно равно р и , то мощность множества состояний будет

n = pV-qV-K (6.7)

В качестве примера рассмотрим устройство Л27. На устройство периодически поступают цифры О и 1, выход его в момент равен сумме по модулю 2 выхода в момент и входа в момент t 2. Обозначая сложение по модулю 2 знаком © 1), Л27 может быть охарактеризовано равенством

Z = X2®-1 = (6.8)

Добавляя несущественные переменные и аг 1, вместо (6.8) получим:

z = f(x, x i, х 2. z i). (6.9)

Входной алфавит в этом случае

. = {0. 1}.

а выходной алфавит

Z={0. 1}.

Множество состояний является множеством всех упорядоченных наборов значений трех переменных (лг 1, аг 2. z i):

5= {(0. 0. 0), (О, О, 1). (О, 1, 0). (О, 1, 1), (1, О, 0), (1. О, 1).

(1. 1. 0). (1. 1. 1)}.

Зависимость между х, s, s и может быть представлена в табличной форме, как показано в таблице 6.1. Столбцы таблицы под представляют все упорядоченные наборы значений трех переменных; каждый набор записан дважды (по одному разу для каждого значения х). Столбцы, озаглавленные «54 1», могут быть заполнены путем воспроизведения ранее заполненных столбцов (таких как х и х {) и

) Сложение по модулю 2 определяется следующим образом: 0®0 = 0, 0®1 = 1, 1®0=1, 1®1=0. Если у прини.мает значение О или 1, то у ® у = 0.

Таблица 6.1 Соотношения между х, s, Sv+i и 2v для Л27

путем использования соотношения (6.8) (для столбца z). Показанную таблицу удобно использовать для определения характеристических функций Д и Д автомата Л27. Например,

Таблица 6.2

Автомат Л27