Размещение состояний автоматов Родин Сергей Борисович

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Родин Сергей Борисович. Размещение состояний автоматов: диссертация ... кандидата Физико-математических наук: 01.01.09 / Родин Сергей Борисович;[Место защиты: ФГБОУ ВО Московский государственный университет имени М.В. Ломоносова], 2017.- 108 с.

Содержание к диссертации

Введение

1 Постановка задачи 17

2 Неизбыточные кодирования 20

2.1 Линейно реализуемые элементы полугруппы Рп 20

2.2 Линейно реализуемые переходные системы 36

2.3 Линейно реализуемые автоматы 52

3 Избыточные кодирования 66

3.1 Линейно реализуемые элементы полугруппы Рп 66

3.2 Линейно реализуемые переходные системы 69

4 Максимальная вариативность относительно кодирования состояний 79

4.1 Критерий свойства максимальности 79

4.2 Линейная реализуемость и свойство максимальности 91

4.2.1 М(п) \ L(n) 91

4.2.2 L(n) \ М(п) 92

4.2.3 М(п) Р L(n) 97

Заключение 105

Список литературы 106

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

Введение к работе

Актуальность. Диссертация посвящена изучению задачи кодирования состояний автоматов.

Абстрактный автомат является достаточно мощным объектом для описания функционирования реальных устройств. Это понятие используется в таких областях как теория сложности, теория алгоритмов, теория языков, теория групп. На практике автомат используется в таких областях как синтез СБИС, теория кодирования, обработка изображений, передача данных. Однако, для практического применения необходимым этапом является синтез автоматов или переход с языка абстрактных автоматов на язык схем.

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

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

В зависимости от условий, накладываемых на получаемую схему, возникает ряд задач, связанных с кодированием состояний автомата: задача противогоночного кодирования, задача монотонного кодирования, задача экономичного кодирования и другие.

В случае противогоночного кодирования требуется найти такое коди-

рование, что при любом переходе автомата из одного состояния в другое переключается только один элемент памяти.

Задача монотонного кодирования состоит в нахождение такого кодирования, что возникаемые функции переходов являются монотонными функциями алгебры логики.

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

Вопрос «простой» реализации автоматов был рассмотрен в работах 60-х годов Стирнса и Хартманиса. В основе исследований лежал метод пар разбиений на множестве состояний автомата. Этот метод был в дальнейшем трансформирован в метод алгебры пар.

Был доказан ряд результатов, связывающий возможность декомпозиции автомата в последовательно-параллельное соединение меньших автоматов с наличием пар покрытий множества состояний с определенными свойствами².

Тот или иной подход к реализации автоматов приводит к возникновению булевых операторов. Суммарная сложность этих операторов и задает сложность реализации автомата. Естественно начинать такого рода исследования с «простейших», линейных операторов. Наиболее полно линейные автоматы изучены в книге А. Гилла «Линейные после-

¹Ashar P., Devadas S., Newton R. A. Sequential Logic Synthesis. Kluwer Academic Publishers Norwell, MA, USA, 1992.

²Хартманис Ю., Стирнс P. Э. Алгебра пар и ее применение к теории автоматов // Кибернетический сборник. 1969. Т. 6. С. 89—111.

довательностные машины»³. Линейным автоматом называется шестерка С = (Ер, Ер, Е, (р,ф, qo), где tp(x, q) = Ах + Bq, ф(х, q) = Cx + Dq, сумма понимается в смысле суммы в поле Галуа GF(p), где p — простое число. В книге введены и изучены понятия эквивалентности, подобия, минимальности, канонической формы, управляемости и предсказуемости линейных автоматов. Отдельно рассмотрены и изучены автономные линейные автоматы и автоматы с нулевым начальным состоянием. Для каждого из классов изучены проблемы анализа и синтеза автоматов. Также отдельно рассматриваются процессы изменения состояний автоматов и развивается теория множества циклов и деревьев.

И в частности, рассмотрен вопрос линейной реализуемости для автоматов, у которых множество входных сигналов — это множество I-мерных векторов над полем GF(p), множество выходных сигналов — это множество m-мерных векторов над полем GF(p), множество состояний содержит р^п элементов. Приводится метод, который в некоторых случаях дает ответ о линейной реализуемости. Таким образом, данный результат не в полной мере решает вопрос о линейной реализуемости автомата.

Другой подход связан с рассмотрением свойств внутренней полугруппы. Внутренняя полугруппа определяется как замыкание отображений множества состояний в себя, определяемых входными символами⁴. Внутренняя полугруппа является инвариантом относительно кодирований состояний. Тогда вопрос линейной реализуемости можно решать через ха-рактеризацию внутренней полугруппы.

В работе Экера⁵ был рассмотрен вопрос о линейно реализуемых автоматах с точки зрения внутренней полугруппы. В частности, приведена характеризация внутренней полугруппы линейно реализуемого автома-

³Гилл А. Линейные последовательностные машины. 4-е изд. Москва «Наука», 1974.

⁴ Арбиб М. Декомпозиция автоматов и расширение полугрупп // Алгебраическая теория автоматов, языков и полугрупп. 1975. С. 46—64.

⁵Ескег К. On the semigroup of a linear nonsingular automaton // Mathematical Systems Theory. 1973. T. 6. C. 353—358.

та в случае, когда внутренняя полугруппа автомата — группа, а именно, группа G изоморфна внутренней полугруппе линейного над полем GF(p) автомата тогда и только тогда, когда:

G содержит нормальную, абелеву подгруппу N, у которой все элементы кроме единичного имеют порядок р;
существует такой элемент с Є G, что N и с образуют G.

Однако, данная теорема не в полной мере решает вопрос о линейно реализуемости автомата, так автомат, внутренняя полугруппа которого удовлетворяет условиям теоремы, не всегда является линейно реализуемым, что было показано в работе Хартманиса и Уолтера⁶. В этой же работе развит подход, предложенный Экером, и сформулирован критерий линейной реализуемости автомата в случае, когда автомат — перестановочный и сильно-связный. Также отметим, что в работе рассматриваются автоматы без выходов или переходные системы. В случае, когда внутренняя полугруппа автомата V — это транзитивная группа G, состояния автомата V могут быть рассмотрены как левые смежные классы группы G по простой подгруппе Н, т.е. переходная система автомата с точностью до изоморфизма определяется группой G, простой подгруппой Н и подмножеством / С G, где G — внутренняя полугруппа, множество смежных классов — множество состояний, подмножество / — множество входов. Переходная система, задаваемая этими объектами, обозначается Vg,hj. Тогда результат может быть сформулирован следующим образом, переходная система Vg,h,i - линейно реализуема над полем GF(p) тогда и только тогда, когда

G содержит нормальную, абелеву подгруппу N, у которой все элементы кроме единичного имеют порядок р;
существует такой элемент с Є G, что N и с образуют G;

⁶Hartmanis J., Walter Н. Group theoretic characterization of linear permutation automata // Journal of Computer and System Sciences. 1973. T. 7, № 2. C. 168—188.

N П Н = е;
/ С TVa для некоторого а Є G.

Данный результат ограничен перестановочными сильно-связными автоматами. Дальнейшее развитие изложенный подход получил в работе Хартфила и Максона⁷. В работе сформулированы две теоремы. Первая — это обобщение результата Экера на полугрупповой случай, а именно существует изоморфизм /3 между полугруппой S =< фо,фі,... ,ф_г > и внутренней полугруппой автомата, линейно реализуемого над полем GF(p) тогда и только тогда, когда S — подполугруппа моноида J = < 0о, N >, где

N — абелева группа, содержащая единичный элемент моноида J, у которой все элементы имеют порядок р;
фоЫ = Ыфо;
если для ф', ф" Є N верно 0^/0_о = 0^//0о, то Ф' = Ф";
{0о, 01, , Фг} ^ ^фо.

Вторая теорема обобщает результат Хартманиса и Уолтера на случай полугрупповых автоматов. Пусть задана полугруппа S, тогда автомат имеющий в качестве внутренней полугруппы полугруппу S определяется, с точность до изоморфизма, полугруппой S, множеством / С S, и левой конгруэнтностью р на S, где / — множество входов, классы эквивалентности, определяемые конгруэнтностью р — множество состояний, умножение в полугруппе S определяет функцию переходов. Такой автомат обозначен через Vs,i,p. В определенных терминах сформулирован критерий линейно реализуемости, а именно автомат Vs,i,p линейно реализуем над полем GF(p) тогда и только тогда, когда S — подполугруппа моноида J =< 0о, N >, где

⁷ Hartfiel D., Maxson С. A Semigroup Characterization of a linearly realizable automaton over GF(p) // Journal of Computer and System Sciences. 1977. T. 14, N^a 1. C. 150—155.

N — абелева группа, содержащая единичный элемент моноида J, у которой все элементы имеют порядок р;

если для ф', ф" Є N верно ф'ф$ = ф^Фо, то ф> = ф";

{0о, фіі , Фг} ^ ^фо;

конгруэнтность р может быть доопределена до левой конгруэнтности р на J таким образом, что р П /і = id, где р — конгруэнтность на J, определяемая правилом: s/it если существует такой элемент ф Є N, что s = ^t.

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

Предыдущие результаты относятся к случаю неизбыточных кодирований, т.е. когда состояния кодируются минимально возможными по длине кодами. Однако, автомат может не являться линейно-реализуемым для неизбыточного кодирования, но «удлинение» кода приводит к линейной реализуемости автомата. С точки зрения полугрупповых свойств наличие такого более длинного кода, приводящего к линейной реализуемости автомата A, эквивалентно существованию линейно-реализуемого автомата, чей гомоморфный образ равен исходному автомату A. В работах⁸,⁹ исследуются гомоморфные образы

⁸Hartmanis J., Davis W. A. Homomorphic images of linear sequential machines // Journal of Computer and System Sciences. 1967. T. 1, N^a 2. C. 155—165.

⁹Hartmanis J., Walter H. Group theoretic characterization of linear permutation automata // Journal of Computer and System Sciences. 1973. T. 7, N^a 2. C. 168—188.

линейно-реализуемых переходных систем. Доказан результат, гомоморфный образ линейно реализуемой переходной системы, не являющийся линейно-реализуемым, есть последовательно-параллельное соединение двух переходных систем, одна из которых либо не содержит обратных связей, либо функция переходов этой переходной системы зависит фиктивным образом от входной переменной. Заметим, что данные результаты приведены для группового случая, т.е. для переходных систем, чья внутренняя полугруппа является группой. Данные результаты задают критерий линейной реализуемости «длинными» кодированиями, однако, не приведены оценки на длину кода, приводящего к линейной реализуемости. А также нет оценок сложности реализации автоматов, не являющихся линейно реализуемыми.

Цель исследования. Основной целью настоящей работы является исследование и совершенствование математических методов, применяемых при решении задачи кодирования состояний автоматов. Тема, объект и предмет диссертационной работы соответствуют следующим пунктам паспорта специальности 01.01.09 — дискретная математика и математическая кибернетика: теория автоматов; теория кодирования (алгоритмические и комбинаторные вопросы, синтез и сложность управляющих систем), в частности, сложность алгоритмов и вычислений). Для достижения поставленной цели в работе сформулированы и решаются следующие задачи.

Нахождение критерия линейной реализуемости автомата посредством неизбыточных кодирований в терминах порождающих внутренней полугруппы

Теоретическая оценка сложности реализации автомата посредством всевозможных однородных кодирований состояний, не обязательно неизбыточных

Алгоритмическая разрешимость задачи распознавания свойства ли-

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

Нахождение критерия максимальной реализуемости автомата в тер
минах порождающих внутренней полугруппы

Научная новизна. Результаты диссертации являются новыми и получены автором самостоятельно. Основные результаты диссертации состоят в следующем:

Сформулирован критерий линейной реализуемости автомата посредством неизбыточных кодирований в терминах порождающих внутренней полугруппы

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

Доказана алгоритмическая разрешимость задачи распознавания свойства линейной реализуемости автомата посредством всевозможных однородных кодирований состояний автомата, не обязательно неизбыточных

Сформулирован критерий максимальной реализуемости автомата в терминах порождающих внутренней полугруппы

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

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

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

Апробация. Основные результаты диссертации докладывались на семинарах и всероссийских и международных конференциях, включая:

научный семинар «Теория автоматов» под руководством профессора В.Б. Кудрявцева, механико-математический факультет МГУ имени М.В. Ломоносова, 2016 г.;

научный семинар «Теория дискретных функций и приложения» под руководством профессора Д.Н. Бабина, старшего научного сотрудника И.Л. Мазуренко механико-математический факультет МГУ имени М.В. Ломоносова, 2016 г.;

научный семинар «Дискретная математика и математическая кибернетика» под руководством профессора В.Б. Алексеева, профессора А.А. Сапоженко, профессора С.А. Ложкина факультет ВМиК МГУ имени М.В. Ломоносова, 2016 г.;

семинар «Дискретный анализ» под руководством профессора СВ. Алёшина, профессора В.А. Буевича, старшего научного сотрудника М.В. Носова, механико-математический факультет МГУ имени М.В. Ломоносова, 2014 г.;

семинар «Компьютерная безопасность» под руководством старшего научного сотрудника А.В. Галатенко, механико-математический факультет МГУ имени М.В. Ломоносова, 2015 г.;

научный семинар «Нейронные сети» под руководством профессора А.А. Часовских, научного сотрудника B.C. Половникова, старшего научного сотрудника А.А. Говорко механико-математический факультет МГУ имени М.В. Ломоносова, 2016 г.;

XI международная конференция «Интеллектуальные системы и компьютерные науки», МГУ имени М.В. Ломоносова, 28 ноября - 2 декабря 2016 г.;

Двенадцатый Международный научный семинар «Дискретная математика и ее приложения» имени академика О. Б. Лупанова, МГУ имени М.В. Ломоносова, 20-25 июня 2016 г.;

Десятый международный научный семинар «Дискретная математика и ее приложения», МГУ имени М.В. Ломоносова, 1-5 февраля 2010 г.;

Международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ акад. В. А. Садовничего, МГУ имени М.В. Ломоносова, 1-5 мая 2009 г.;

VII Международный семинар «Дискретная математика и ее приложения», МГУ имени М.В. Ломоносова, 9 января-2 февраля 2001 г.

Публикации. Основные результаты диссертации опубликованы в 4 печатных работах автора [1—4], из них 3 [1—3] в научных журналах из списка, рекомендованного ВАК ГФ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 31 наименования. Общий объем диссертации составляет 108 страниц.

Линейно реализуемые переходные системы
Сгруппируем эту сумму по степеням х, где 0 / к — 1. Коэффициент при каждой степени есть линейная комбинация эд, где 0 / к — 1. Коэф фициент при степени х1 есть значение 1-й функции из множества J-s(Fo). А следовательно, данная функция является линейной булевой функцией переменных до, , Qk-i. Таким образом, показано, что всякое отображе ние, у которого соответствующий многочлен над полем Галуа — это ли нейная комбинация многочленов вида х1, где і = 0,... ,к — 1, и констан ты с Є F2fc, является линейно реализуемым посредством кодирования FQ. Согласно лемме 2 число различных отображений на n-элементном множе стве, линейно реализуемых посредством кодирования Fo, равно nlog2 +1. В силу однозначности и единственности многочлена над полем Галуа, со ответствующего данному отображению, получаем, что для отображений, линейно реализуемыx посредством кодирования Fo, соответствующий мно гочлен имеет указанный вид. Утверждение доказано.
Как видно из примера 4 подстановка /О 1 2 3 4 5 б 7\ 0 2 4 6 3 1 7 5 линейно реализуема. Соответствующий ей многочлен над полем Fg есть 2 х. Следствие 1. Подстановки /г+ Є Н+ линейно реализуемы посредством кодирования Fo и J-h+(Fo) = {хо + Co,#i + Сі,...,ж -і + ck-i\, (со, сі,..., Ck-i) = Fo(c). Лемма 5. Пусть заданы отображения р\, р2 множества Еп в себя и кодирование F. Тогда фр1.Р2 = Ф ІФт).
Доказательство. Сначала докажем утверждение для случая линейной реализуемости отображения посредством кодирования Fo. Заметим, что s_p0 — тождественная подстановка.
Пусть р линейно реализуема посредством FQ. Согласно лемме 4 соответствующий ей многочлен над полем Галуа F2k является линейной комбинацией многочленов вида х2, где г = 0,.., & — 1, и константы с Є F2fc. Пусть соответствующий многочлен имеет вид fp(x) = Со + Хл=і с .
Согласно определению Н+ — множество подстановок, соответствующих многочленам х+с над полем Галуа Fn, где с Є E2k — константа. Без ограничения общности рассмотрим подстановку hC, соответствующую многочлену X + с.
Так как данное равенство верно для любого q и d и не зависит от q, то hc-p = p-hc/. Следовательно, для каждого с Є Е2к существует такое с , что hc р = р hc/. Отсюда следует, что Н+р с рН+.
Докажем обратное утверждение. Пусть Н+р С рН+, т.е. для каждого с Є Е2к существует такое с , что hc р = р hc . Предположим, что отображение р не является линейно реализуемым. Тогда среди функций J ,(Fo) найдется нелинейная функция /. Согласно следствию 1 и следствию 2 f{xo + Со, Х\ + Сі, . . . , Ж&-1 + Cfc_l) = /(жо, Жі, ..., rr _i) + (І, где со, Сі,... , Cfc_i, (і Є Е2. Поскольку функция / нелинейная, в ее полиноме Жегалкина найдется член, являющийся произведением не менее двух сомножителей. Без ограничения общности считаем, что среди этих множителей присутствуют хо и х\. Тогда полином можно преобразовать следующим образом:
Докажем утверждение в общем случае. Согласно лемме 3 булев оператор, который кодирование F сопоставляет отображению р, совпадает с булевым оператором, который кодирование Fo сопоставляет отображению sF -p-sp. Отображение sF -p-sp линейно реализуемо посредством кодирования Fo тогда и только тогда, когда H+sF -p-sp С sF -p-spH+. Следовательно, для каждого с Є Е2к существует такое с, что hc-sF -p-sp = sF -p-sp-hci; тогда sp hc sF p sp = p sp hc/, sp hc sF p = p sp hc/ sF . Заметим, что SF hc- sF ,SF- hcj sF Є H F. Так как подстановка SF задает изоморфное отображение Н+ на Н , то Н р С рН . Лемма 7. Пусть задано отображениер множества Q = {0,1,... ,п —1} в себя, где п = 2к. Тогда р = с h, где с(0) = 0, h Є Н+.

Линейно реализуемые автоматы
Доказательство. Пусть автомат A = (Е , {0,1,... ,п — 1}, Е2, (р, ф): где п = 2к, линейно реализуем. Тогда существует такое кодирование F, что все элементы J-A(F) являются линейными функциями алгебры логики. В частности, линейна функция /&, соответствующая выходной функции ф. Следовательно, fk{x, qo, Qi, qk-i) = Со+Сі-ж+С2- о+Сз- і + .. .+Ck+i-qk-i-Значит, фо(х) = co+ci-x+(3: где /3 — значение С2-до+сз- і + - -+с;+гФг-і на коде состояния 0 при кодировании F. Функция, реализуемая в состоянии q: ЄСТЬ фд(х) = Со + С\ X + Q) + С\ X + С2 Сїо + Сз OL\ + + Q;+l CKfc-l, где («о, скі,..., CKfc-i) — код состояния q при кодировании F. Таким образом, в состояниях реализуется либо функция со + Сі-ж, либо со + Сі Ж + l. Заметим, что С2 о + Сз і + + с/г+і -1 принимает значение 1 на половине наборов («о, «і,..., a:fc_i), где CKJ Є і?2, а на другой половине наборов принимает значение 0. Так как со + с\ х + 1 = со + с\ х) а со + с\ х = CQ + с\ х + 1, то \QihA = \QJT\. Определение 21. Пусть задан линейно реализуемый автомат A = (i?2, {0,1,..., п — 1}, i?2, ty?, ф)- Определим выходной предикат pout : {0,1,..., п — 1} — i?2 правилом pout(q) = ф(0, q). Пример 19. Выходной предикат автомата из примера 15 есть
Функция f(qo, #1, 2) = 7o + 7i + 7i 2 + qo Qi. Определение 23. Назовем предикат pout : {0,1,..., n — 1} —i?2 линейно реализуемым посредством кодирования F или просто линейно реализуемым, если существует такое кодирование F, что функция ф является линейной функцией алгебры логики.
Доказательство. Пусть автомат A = (Е , {0,1,... ,п — 1},Е2,(р,ф): где п = 2 , линейно реализуем. Тогда существует такое кодирование F, что все элементы J-A(F) являются линейными функциями алгебры логики. В частности, линейна функция /&, соответствующая выходной функции ф. Значит, fk(x,qo,qi, , qk-i) = Со + Сі-ж + С2- о + Сз- і + - + С;+і-Фг-і- Заметим, что ф(х ) = fk+i(x,F(q)). Тогда предикатpout(q) = fk+i(0,F(q)) = Co+C2 QO + c3 Ql + + ck+l Фг-1, ГДЄ («о, CKi, . . . , Q -l) — КОД СОСТОЯНИЯ (/ При КОДИ ровании F. Заметим, что функцияpout(q) = Со + С2- о+Сз- і + - .+Ck+i-qk-i принимает значение 1 на половине наборов (ско, скі,..., ск -і), где CKJ Є і?2, а на другой половине наборов принимает значение 0. Отсюда следует утвер ждение леммы.
Лемма 19. Пусть автомат A = (і?2, {0,1,..., п — 1}, i?2, ty?, V0 линейно реализуем. Тогда существуют такие а, Ъ Є і?2, что ф(х ) = pout{q) + ах + Ъ для всех q Є {0,1,..., п — 1}.
Доказательство. Пусть автомат A = (і?2, {0,1,... ,п — 1}, і?2, ty?, V0? гДе п = 2к, линейно реализуем. Тогда существует такое кодирование F, что все элементы J-A(F) являются линейными функциями алгебры логики. В частности, линейна функция /&, соответствующая выходной функции ф. Значит, fk(x,qo,qi,... ,qk-i) = Со + Сі-ж + С2- о + Сз- і + - .+Ck+i-qk-i- Заметим, что (ж,д) = fk(x,F(q)). Тогда предикат pout(q) = fk+i(0,F(q)) = Со + C2-qoJcC2,-q\Jc.. .+Ck+\-qk-\- Следовательно, ф(х ) = pout{q)+CQ+c\-x. П
Пусть задан автомат A = (i?2, {0,1,... ,п — 1}, і?2, ф,Ф), где п = 2к. Автомат линейно реализуем посредством кодирования F тогда и только тогда, когда переходная система VA = (i?2, {0,1,..., п — 1}, (р) линейно реализуема посредством кодирования F, существуют такие а,(3 Є Е і и предикат pout : Q — E i, что ф(х,q) = pout(q) + а х + (3 для каждого q Є {0,1,... ,n — 1}, предикат pout линейно реализуем посредством кодирования F.
Доказательство. Пусть автомат линейно реализуем посредством кодирования F. Тогда элементы T F) являются линейными функциями алгебры логики. Рассмотрим переходную систему VA = (Е2, {0,1,..., п — 1}, (/?). Несложно видеть, что J vA{F) является подмножеством множества J-A(F). Отсюда следует линейная реализуемость переходной системы VA.
Существование констант а,(3 и предиката pout : Q — Е2 следует из теоремы 19, причем предикат pout(q) = /&((), F(q)), где fk Є J-A{F). А значит, pout(q) линейно реализуем посредством кодирования F. Докажем теорему в обратную сторону. Пусть переходная система УA = (i?2, {0,1,... ,п — 1}, (/?) линейно реализуема посредством кодирования F. Согласно определению 11 все элементы J-vA{F) есть линейные функции. Согласно определению 17 функции J-v F) являются первыми к функци ями множества J-A(F). Покажем, что функция /&, соответствующая вы ходной функции ф, также является линейной функцией. Согласно усло вию теоремы существуют такие а,(3 Є Е і и предикат pout : Q — i?2, что i/j(x,q) = pout(q) + а х + (3 для каждого q Є {0,1,... , n — 1} и преди кат pout линейно реализуем посредством кодирования F. Значит, функ ция / „t(a:o, , OLk-i) = pout(F l(ao,... , (ik-i)) — это линейная функция. ф{а) F l(a,Q,..., ctk-i)) = pout(F l(ao,..., cxk-i)) + OL a + /3. А значит, ift(a, F l(ao}..., ctk-i)) — это линейная функция. П
С другой стороны в примере 9 было показано, что переходная система Уд линейно реализуема посредством кодирования F. Выходная функция автомата Л имеет вид ф(х, q) = pout(q), где q 0 1 2 3 4 5 6 7 pout(q) 0 0 1 0 1 1 1 0 т.е. a = 0,/3 = 0 и предикат pout(q) линейно реализуем посредством кодирования F. Следствие 4. Пусть A(n) — множество нумерованных автоматов с п состояниями с входным алфавитом Е2 и выходным алфавитом Е . Число линейно реализуемых автоматов с п = 2к состояниями есть о(A(п)).
Доказательство. Пусть задан автомат A = (Е , {0,1,... ,п — 1}, і?2, ty?5 V0. Автомат полностью определяется переходной системой (i?2, {0,1,... ,п — 1}, (/?) и функцией г\) : i?2 х Еп — Е . Согласно лемме 12 число различных переходных систем есть п2п. Число различных выходных функций есть 22п. Следовательно, число автоматов с п состояниями с входным алфавитом Еч и выходным алфавитом Е2 равно п2п 22п = (2п)2п.
Как было показано в теореме 3, линейно реализуемый автомат определяется линейно реализуемой переходной системой, предикатом pout : Q — Е2 и константами а,(3 Є Е . Число линейно реализуемых переходных систем с входным алфавитом Еч и алфавитом состояний Еп не превосходит — niog2(n)+2 . п _ 2 Число предикатов pout : Q — Е2 не превосходит С%. Число различных констант а,/3 равно 22. Следовательно, число линейно реализумых автоматов не превосходит

Линейно реализуемые переходные системы
Заметим, что внутренняя полугруппа переходной системы V есть Sn, как транспозиция (0 1) и цикл (01 ... п — 1) порождают Sn [14]. Согласно замечанию 2, переходная система V обладает свойством максимальности. Теперь покажем, что данная переходная система не является линейно реализуемой. Согласно теореме 1, если переходная система V линейно реализуема, то найдется такие подстановки s и h Є s lH+s, что pi = ро h. Так как для данной переходной системы порождающие ро и р\ — подстановки, то найдется такая подстановка s, что р$ р\ Є s lH+s. Найдем указанное
Переходная система, обладающая свойством максимальности, но не являющаяся линейно реализуемой произведение порождающих Ро - i = (0 1)(0 ... п — 1) = (02 ... п — 1), т.е. PQ р\ — это цикл длины п — 1. Подстановки, принадлежащие Н+, представляют произведение п/2 транспозиций. Поскольку при сопряжении цикловая структура подстановок сохраняется [14], то не существует таких подстановок s и h Є Н+, что р$ -р\ = s l h- s. Следовательно, построенная переходная система не является линейно реализуемой.
Для произвольного п = 2к приведем пример линейно реализуемой переходной системы, но не обладающей свойством максимальности. Обозначим через sx2 подстановку, соответствующую многочлену х1 над полем Га луа Fn. Обозначим через hx+c подстановку, соответствующую многочлену х + с над полем Галуа Fn, где с ф 0. Рассмотрим нумерованную переходную систему V = (Е2,{0,1,... ,п — l},tp), чья функция переходов определяется как: (/9(0, q) = sx2{q) ip(l,q) = hx+c{sx 2{Q)) Согласно построению переходной системой для ее порождающих верно равенство р\ = sx2 hx+s = Ро hx+c, причем hx+c Є Н+. Согласно лемме 4 отображение линейно реализуемо посредством стандартного кодирования Fo тогда и только тогда, когда соответствующий ему многочлен над полем Галуа F2fc является линейной комбинацией многочленов вида х2, где і = 0,.., к — 1 и константы с Є F2k. Следовательно, набор J-po(Fo) = {fi х (go, qi-, , qn-\)i 0 і к — 1}, где (go, qi-, Qn-i) — код состояния при «стандартном» кодировании Fo, состоит из линейных функций, т.е. подстановка ро линейно реализуема. Согласно следствию 1 J hx+c{Fo) = {fi ж+с( о, qi-, , Qn-i) = Qi + Ы, 0 і к — 1}, где (ho, hi, ...hk) = Fo(c). Так как pi — i x-\-c\ x yl)), то согласно следствию 2 J- Fo) = {fix(qo,qi, , 7n-i) + hi,0 і к — 1}, где (ho,hi, ...hk) = Fo(S). Следовательно, набор J Fo) состоит из линейных функций, т.е. подстановка pi линейно реализуема. Согласно теореме 1 переходная система V линейно реализуема. Теперь покажем, что подстановка, соответствующая многочлену х + 1, коммутирует с ро и pi. Обозначим ее через hx+i. Для каждого q Є Fn верно равенство hx+1(p0(q)) = p0(q) + 1 = q2 + 1. С другой стороны для каждого q Fn верно p0(hx+1(q)) = p0(q + 1) = (q + 1)2. Так как для элементов a,b поля Галуа Fn верно равенство (a+b)2j = a2j +b2j [13], то p0(hx+1(q)) = q2 + 1. Отсюда следует, что hx+1(p0(q)) = q2 +1 = p0(hx+1(q)) для всех q Fn, т.е. hx+1 коммутирует с p0. Теперь покажем, что hx+1 коммутирует с p1. hx+1(p1(q)) = p1(q) + 1 = hx+c(p0(q)) + 1 = p0(q) + c + 1 = q2 + c + 1. С другой стороны для каждого q Fn верно p1(hx+1(q)) = p1(q + 1) = hx+c(p0(q + 1)) = p0(q + 1) + c = (q + 1)2 + c + 1. Так как для элементов a,b поля Галуа Fn верно равенство (a+b)2j = a2j +b2j [13], то p1(hx+1(q)) = q2 + 1 + c = q2 + c + 1. Отсюда следует, что hx+1(p1(q)) = q2 + 2 = p1(hx+1(q)) для всех q Fn, т.е. hx+1 коммутирует с p1. Следовательно согласно теореме 6 построенная переходная система не обладает свойством максимальности. Пример 29. На рисунке 4.4 изображена переходная система VL\M, построенная описанным выше способом для n = 8 и c =
Для произвольного п = 2к приведем пример линейно реализуемой переходной системы, обладающей свойством максимальности. Мультипликативная группа F n поля Fn циклическая. Обозначим через а образующий элемент. Обозначим через sa.x подстановку, соответствующую многочлену a x над полем Галуа Fn. Обозначим через hx+\ подстановку, соответствующую многочлену х + 1 над полем Галуа Fn. Данная подстановка имеет следующий вид (01)(23)... (п — 2п — 1). Рассмотрим нумерованную переходную систему V = (Е2, {0,1,... ,п — 1}, (/?), чья функция переходов определяется как: (/9(0, q) = sa.x(q) cp(l,q) = hx+i(sa.x(q)) Согласно построению переходной системой для ее порождающих верно равенство р\ = sa.x hx+\ = ро /іж+і, причем hx+\ Є Н+. Согласно лемме 4 отображение линейно реализуемо посредством стандартного кодирования Fo тогда и только тогда, когда соответствующий ему многочлен над полем Галуа F2k является линейной комбинацией многочленов вида х2, где і = 0,.., к — 1 и константы с Є F2k. Следовательно, набор
Следовательно, fs(pl0(a)) = s(pl0(a)) = pl0(a) для любого / Є TV. Так как Po(q) = а q, то р10(а) = al l. Значит, для любого / Є N верно, что fs(pb(cL)) = s(Po(a)) = d. Принимая во внимание, что а — порождающий элемент мультипликативной группы, s(q) = q для всех q Є F n. Отсюда следует, что переходная система обладает свойством максимальности.
На рисунке 4.5 изображена переходная система У, построенная описанным выше способом для п = 16. Поле Галуа F\ построим как расширение i 2 c помощью многочлена хА + х + 1. Приведем множества Н+ и Н для поля FIQ. Обозначим подстановку, соответствующую многочлену / над полем Галуа, через hf.

Линейная реализуемость и свойство максимальности
Для произвольного п = 2к приведем пример линейно реализуемой переходной системы, но не обладающей свойством максимальности. Обозначим через sx2 подстановку, соответствующую многочлену х1 над полем Га луа Fn. Обозначим через hx+c подстановку, соответствующую многочлену х + с над полем Галуа Fn, где с ф 0. Рассмотрим нумерованную переходную систему V = (Е2,{0,1,... ,п — l},tp), чья функция переходов определяется как: (/9(0, q) = sx2{q) ip(l,q) = hx+c{sx 2{Q)) Согласно построению переходной системой для ее порождающих верно равенство р\ = sx2 hx+s = Ро hx+c, причем hx+c Є Н+. Согласно лемме 4 отображение линейно реализуемо посредством стандартного кодирования Fo тогда и только тогда, когда соответствующий ему многочлен над полем Галуа F2fc является линейной комбинацией многочленов вида х2, где і = 0,.., к — 1 и константы с Є F2k. Следовательно, набор J-po(Fo) = {fi х (go, qi-, , qn-\)i 0 і к — 1}, где (go, qi-, Qn-i) — код состояния при «стандартном» кодировании Fo, состоит из линейных функций, т.е. подстановка ро линейно реализуема. Согласно следствию 1 J hx+c{Fo) = {fi ж+с( о, qi-, , Qn-i) = Qi + Ы, 0 і к — 1}, где (ho, hi, ...hk) = Fo(c). Так как pi — i x-\-c\ x yl)), то согласно следствию 2 J- Fo) = {fix(qo,qi, , 7n-i) + hi,0 і к — 1}, где (ho,hi, ...hk) = Fo(S). Следовательно, набор J Fo) состоит из линейных функций, т.е. подстановка pi линейно реализуема. Согласно теореме 1 переходная система V линейно реализуема.
Теперь покажем, что подстановка, соответствующая многочлену х + 1, коммутирует с ро и pi. Обозначим ее через hx+i. Для каждого q Є Fn верно равенство hx+1(p0(q)) = p0(q) + 1 = q2 + 1. С другой стороны для каждого q Fn верно p0(hx+1(q)) = p0(q + 1) = (q + 1)2. Так как для элементов a,b поля Галуа Fn верно равенство (a+b)2j = a2j +b2j [13], то p0(hx+1(q)) = q2 + 1. Отсюда следует, что hx+1(p0(q)) = q2 +1 = p0(hx+1(q)) для всех q Fn, т.е. hx+1 коммутирует с p0.
Теперь покажем, что hx+1 коммутирует с p1. hx+1(p1(q)) = p1(q) + 1 = hx+c(p0(q)) + 1 = p0(q) + c + 1 = q2 + c + 1. С другой стороны для каждого q Fn верно p1(hx+1(q)) = p1(q + 1) = hx+c(p0(q + 1)) = p0(q + 1) + c = (q + 1)2 + c + 1. Так как для элементов a,b поля Галуа Fn верно равенство (a+b)2j = a2j +b2j [13], то p1(hx+1(q)) = q2 + 1 + c = q2 + c + 1. Отсюда следует, что hx+1(p1(q)) = q2 + 2 = p1(hx+1(q)) для всех q Fn, т.е. hx+1 коммутирует с p1. Следовательно согласно теореме 6 построенная переходная система не обладает свойством максимальности. Пример 29. На рисунке 4.4 изображена переходная система VL\M, построенная описанным выше способом для n = 8 и c = 3. Функция переходов VL\M определяется как:
Для произвольного п = 2к приведем пример линейно реализуемой переходной системы, обладающей свойством максимальности. Мультипликативная группа F n поля Fn циклическая. Обозначим через а образующий элемент. Обозначим через sa.x подстановку, соответствующую многочлену a x над полем Галуа Fn. Обозначим через hx+\ подстановку, соответствующую многочлену х + 1 над полем Галуа Fn. Данная подстановка имеет следующий вид (01)(23)... (п — 2п — 1). Рассмотрим нумерованную переходную систему V = (Е2, {0,1,... ,п — 1}, (/?), чья функция переходов определяется как:
Согласно построению переходной системой для ее порождающих верно равенство р\ = sa.x hx+\ = ро /іж+і, причем hx+\ Є Н+. Согласно лемме 4 отображение линейно реализуемо посредством стандартного кодирования Fo тогда и только тогда, когда соответствующий ему многочлен над полем Галуа F2k является линейной комбинацией многочленов вида х2, где і = 0,.., к — 1 и константы с Є F2k. Следовательно, набор J-po(Fo) = {fia x{qo,Qii- іQn-\)i0 і к — 1}, где (go, qi-, Qn-i) — код состояния при «стандартном» кодировании Fo, состоит из линейных функций, т.е. подстановка ро линейно реализуема. Согласно следствию 1 J K+1{Fo) = if] x+1{qo, qi-, , qn-\) = qi + Ы,0 і к — 1}, где (ho, hi, ...hk) = Fo(l). Так какрі = hx+i(sa.x(q)), то согласно следствию 2 J-pi(Fo) = {fiax(qo,qi,... ,qn-i) + Ы,0 і к — 1}, где (ho, hi, ...hk) = Fo(l). Следовательно, набор J-pi(Fo) состоит из линейных функций, т.е. подстановка pi линейно реализуема. По теореме 1 переходная система V линейно реализуема. Пусть подстановка s коммутирует с ро и pi. Согласно построению ро соответствует многочлену а х, pi соответствует многочлену а х + 1, т.е. для любого q Є Еп Po(q) = a q, Pi(q) = a q + 1. Обозначим через fs многочлен над полем Галуа Fn, соответствующий подстановке s, a через f l многочлен над полем Галуа Fn, соответствующий подстановке s l. Обозначим через qo прообраз «0» при отображении s, т.е. s{Qo) = fs{qo) = 0. Поскольку s коммутирует с ро = sa.x, то верно
Рассмотрим правую и левую часть равенства (4.2) на элементе qo и перепишем его в виде многочленов: 17 (а (fs(qo))) = 17 (о. о) = / (о) = qo, Роіяо) = а ПоСледовательно, qo = а qo, где а 0. Отсюда следует, что qo = 0 и /s(0) = s(0) = 0. Поскольку s коммутирует с р\ = sa.x+i, то верно s р\ s = р\. (4.3) Рассмотрим правую и левую часть равенства (4.3) на элементе 0 и перепишем его в виде многочленов: І7 (а (Л(0)) + 1) = f (а 0 + 1) = / (1), Рг(0) = а 0 + 1 = 1. Следовательно, /s_1(l) = 1. Отсюда следует, что /s(l) = s(l) = 1. Рассмотрим правую и левую часть равенства (4.2) на элементе 1 и перепишем его в виде многочленов І7 (а (Л(1))) = 17 (а і) = І7 (а) = а і = а Отсюда следует, что fs(a) = s(a) = a. Заметим, что a = p0(1). Рассмотрим правую и левую часть равенства (4.2) на элементе pl0(a) S ( Т)с\ ( S ( CL ))) —— S (29 n (CL)) —— 29 n (CL) Следовательно, fs(pl0(a)) = s(pl0(a)) = pl0(a) для любого / Є TV. Так как Po(q) = а q, то р10(а) = al l. Значит, для любого / Є N верно, что fs(pb(cL)) = s(Po(a)) = d. Принимая во внимание, что а — порождающий элемент мультипликативной группы, s(q) = q для всех q Є F n. Отсюда следует, что переходная система обладает свойством максимальности.
На рисунке 4.5 изображена переходная система У, построенная описанным выше способом для п = 16. Поле Галуа F\ построим как расширение i 2 c помощью многочлена хА + х + 1. Приведем множества Н+ и Н для поля FIQ. Обозначим подстановку, соответствующую многочлену / над полем Галуа, через hf. Н+ = {hx-\-o = е, hx+i