Об условиях разрешимости автоматных уравнений

1. Общая характеристика работы.

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

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

В работе используются методы теории автоматов, теории графов и теории алгоритмов.

Задача была впервые поставлена в общем случае академиком В. Б. Кудрявцевым в [3]. Частный случай решаемой задачи был рассмотрен А. К. Григоряном в [5] и [6]. В этих работах решаются автоматные уравнения с одной неизвестной для 4 видов схем. Позже A.C. Подколзин и Ш. М. Ушчумлич в [7] ввели понятие автоматного уравнения, отличное от понятия автоматного уравнения, рассматриваемого в этой работе, и описали алгоритм, перечисляющий все решения такого уравнения с одной неизвестной. Кроме того, Н. В. Евтушенко в своих работах [8] - [10] рассматривала автоматные уравнения для разных классов языков, в том числе и для недетерминированных автоматов и получила необходимое условие для недетерминированного автомата, чтобы он был решением уравнения.

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

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

1. Предложен алгоритм для решения автоматного уравнения с одной неизвестной.

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

Автор выражает благодарность профессору В. А. Буевичу за постановку задачи, профессору Э. Э. Гасанову и академику В. Б. Кудрявцеву за ценные замечания при написании этой работы.

2. Содержание работы.

Алфавит {0,., к — 1} будем обозначать E??.

Пусть, А — произвольный конечный алфавит. Обозначим А* множество всех слов, а ^4°° - множество всех сверхслов над данным алфавитом.

Пусть a, b G А*, тогда |а| будем обозначать длину слова a. a ab — конкатенация этих слов.

Функция /: А* —"• В* называется детерминированной, если она удовлетворяет следующим условиям.

1) Если, а б А*, то |/(а)| = (а|.

2) Пусть ai = а (1). а (к) и а2 = а'(1). .a'(fc), /(ai) = b (l).b (k) и /(«г) = b'(l). .b'{k). И пусть при всех s, 1 < s < к, если а (1) = а'(1), ¦., a (s) = a'(s), то Ъ (1) = 1/(1),., 6(s) = V (s).

Детерминированная функция д: А* В* называется частичной для детерминированной функции /: А* —> В*, если существует такое 7 G А*. что для любого слова a G A* /(7a) = f (y)g (ce).

Детерминированная функция называется ограниченно-детерминированной, или о.-д. функцией, если она имеет конечное множество частичных функций.

Детерминированным автоматом (ДА, или просто автоматом) называется шестерка (A, Q, В, ф, ф, q°). где:

А — конечный входной алфавит;

В — конечный выходной алфавит;

Q — конечное множество состоянийф: Q х А—> Q — функция переходов: ф: Q х АВ — функция выходовq° G Q — начальное состояние.

В случае, когда Л = А х А2 х. х Ап, будем говорить, что автомат имеет п входов и алфавит г'-ого входа.

В случае, когда В = В х В2 х. х Вгп, будем говорить, что автомат имеет т выходов и алфавит г-ого выхода — Вг. При этом функция выходов ф: Q х, А —"¦ В разбивается на т функций выходов фг: Q х, А —> Вг, 1 < i < т следующим образом. Если для некоторых, g G Q и a G /1 Ф (<1, о) = (bi, b2,., bm), то а) = Ьъ. То есть ^ = ^ х ф2 х. х.

Множество автоматов с входным алфавитом, А и выходным В обозначим Р (А, В).

Обозначим Р множество всех таких автоматов, каждый вход и выход которого имеет алфавит Е^ где к — некоторое натуральное число, для каждого входа или выхода своё.

Пусть здесь и далее v = (A, Q, В, ф^ ?/-, q°) — детерминированный автомат.

Обозначим Ф: А* —> Q функцию, возвращающую состояние Ф (а), в котором окажется автомат v, если на вход ему подать слово а. Более строго:

1) Ф (А) = q°. где, А — пустое слово:

2) Ф (а (1). а (п — 1) а (тг)) = ^(Ф (а (1). а (п — 1)), а (п)).

Обозначим Ф*: А* —" Q* функцию, возвращающую последовательность состояний Ф*(а), через которые проходит автомат г>, если на вход ему подать слово а. Более строго:

1) Ф*(Л) = 5°, где Л — пустое слово;

2) Ф*(а (1). а (п — 1) а (п)) = Ф*(а (1). а (п — 1))Ф (а (1). а (п)).

Обозначим Ф: А* —> В функцию, возвращающую последнюю букву.

Ф (а), выданную на выходе автомата v, если на вход ему подать слово а. Более строго:

Ф (а (1). .а (п — 1) а (гс)) = ф (Ф (а (1) .а (п- 1)), а (п)).

Обозначим Ф*: А* —> В* функцию, возвращающую выходную после-довательттость Ф*(а), выданную на выходе автомата v, если на вход ему подать слово а. Более строго:

1) Ф*(Л) = Л, где Л — пустое слово;

2) Ф*(а (1). а (п — 1) а (тг)) = Ф*(а (1). а{п — 1))Ф (а (1). а (п)).

Функцию Ф* будем называть функцией автомата у.

В [4] доказывается, что функция любого автомата всегда является о.-д. функцией, и наоборот: для любой о.-д. функции существует автомат, функцией которого она является.

Два автомата называются эквивалентными, если их автоматные функции совпадают.

Определим некоторые элементарные операции над автоматами, с помощью которых будут строиться автоматные схемы:

Операцией добавления фиктивного входа (см. рис. 1) будем называть функцию, отображающую множество Р (А, В) во множество Р (А х А', В), такую что произвольный автомат у = (А, С^ В, ф: ф, (р) переходит в автомат у' = (А х А', ф, В, ф', ф д°), такой что для всех д е <5, а? Л и а' € Л' выполняется:

Ф'{Ъ а')) = а);

Ф'(<1, {а, а')) = ^(<?, а).

Таким образом, операция добавления фиктивного входа просто добавляет ещё один вход к автомату, при этом новый вход становится несущественным. Обозначается данная операция.

Операцией изъятия выхода (см. рис. 2) будем называть функцию, отображающую множество Р (А, В х В') во множество Р (А, В), такую что произвольный автомат у = (А, В х. х Вт, ф, ф, д°) переходит в автомат у' = (А, х. х Вт-1,ф, ф', д°), такой что для всех д е, а € А и 1 < г < т — 1 выполняется: ФМ, а).

Таким образом, операция изъятия выхода просто игнорирует последний выход автомата. Обозначается данная операция 2%.

Пусть Ап-1 = Ап. Операцией склеивания входов (см. рис. 3) будем называть функцию, отображающую множество Р{А х. х Ап 1 х Ап, В) во множество Р (А х. х Ап-1,В), такую что произвольный автомат у = (Ах х. х Ап 1 х Ап, В, ф, ф, д°) переходит в автомат у' = (Ах х. х Ап1, В, ф', ф5°), такой что для всех д € <5 и <2г- € А^ выполняется: д, (си,., апх)) = </>(д, (ах,., о&bdquo-1, а"х)) — ф'(д, (а1?., апх)) = ^(<7, («1, • • •, апх)). а, а а i i i i i i 1 г 1 1 1 1 1— 1 1 1 1 ¦ ¦ ¦ ¦

1 1 1 1 1 1 а, а а, а 1 1 1 1 1 1 ¦ ¦ ^ ¦ ¦ ¦ ¦ ¦ ¦

Рис. 1:

Рис. 2:

Рис. 3:

Рис. 4:

Рис. 5:

Рис. 6:

Рис. 7:

Рис. 8:

Обозначается данная операция З^.

Пусть произвольная перестановка элементов множества.

1,., п}. Операцией переименования входов (см. рис. 4) будем называть функцию, отображающую множество Р (А^ 1 х. х В) во множество Р{А х. х Ап, В), такую что произвольный автомат v — (А^ х. х А{п, В, ф, ф, д°) переходит в автомат у' = х. х Ап, СВ, ффд°). такой что для всех д € ф. а{? А{ выполняется:

Ф'{<1, («Ъ • • • > «п)) = </>(4, (а'гп — - •, Ог&bdquo-)) — аь ., ап)) = ^(д, (а^,• • •, а*п)).

Обозначается данная операция у' = 4х-(г-, ?1,., гп).

Пусть ,., 2 т — произвольная перестановка элементов множества {1 ,., т}. Операцией переименования выходов (см. рис. 5) будем называть функцию, отображающую множество Р (А, В^ х. х Вгш) во множество Р (А, В х. х такую что произвольный автомат у = (А, (5, В^ х. х £?гт, ф, д°) переходит в автомат у' = (А, С?, ВХ. х Вт, ф, д°). такой что для всех д € <5, а€/1и1<&<�т выполняется: а).

Обозначается данная операция 5е, г/ = .

Операцией расщепления выхода (см. рис. 6) будем называть функцию, отображающую множество Р (А, В х. х Вгп) во множество Р (А, В х. х Вт х Вт+х). такую что произвольный автомат у = (А, В х. х Бт, ф, ф, д°) переходит в автомат у' = (А, <5, х. х Вт х Вт+1, ф, ф', д°). такой что для всех д е, а е, А выполняется:

•(д, а) = ^-(д, а), если1 < ^ < т,.

Обозначается данная операция Пусть = (Д <2, х. х Вт, ф, д°), г = (С1 х. х Сп, В, фг, фг, д5).

Скажем, что автомат 7ъ (у, г, г, э) = (А'^ х С2г, Вг, ф', ф', (д°, д®-)} получен из автоматов и и г с помощью операции последовательного соединения (или выход г автомата у соединен со входом у автомата г, см. рис. 7). если выполняются следующие условия.

1) Вг С Су.

2) А' = А X Сг х. х С/1 х х. х Сп.

3) I)' = X. .. X Вт X I).

4) <£'((д, дг), (а, сь ., с,-ь с,-+ь., сп)) = (0(д, а), (сь ., ?/>г-(д, а), ., сп))).

5) Если к < т, то ^¿-.((д, (а, сь ., с7-ь с,-+ь., с&bdquo-)) = ^(д, а).

6) ^т+жз) &)> о, сь. .. , су+1,. .. , с&bdquo-)) = (С1, • • •, Сэ-иФМ, а), 1,., Сп)).

Будем говорить, что в состоянии д автомата г> = (Л1 х. х Ап, С^, В х. х £?то, ф, ф,(р) г-тый выход не зависит от ^'-того входа, если для любых а>к € Ак (1 < к < п) и любого, а е А, — выполняется равенство.

Ь • • •, %+ь • • •, Йп)) = («1, • ¦ ¦, О-з-Ъ а> %+Ь ¦ ¦ • > ¿-п)).

Автомат у = (А х. х С^, Вх. .х Вт, ф, ф, д°) будем называть Ц-корректным для обратной связи, если выполняются следующие условия.

1) В состоянии д° г-тый выход не зависит от j-rroтo входа.

2) Если в состоянии д? <3 г-тый выход не зависит от^-того входа, то для любых ак € А}ц (1 < к < п) в состоянии д, (аь ., ^¿-(д, Оъ • • •, ь ., ап)), а-,+1, ., ап)) г-тый выход тоже не зависит от^-того входа.

Пусть автомат у = (А х. х Ап, С}, Вх. .х Вт, ф, д°) ¿-^'-корректен для обратной связи. Будем говорить, что автомат г, = (А', <3', х. .хВт, ф', ф', д°) получен из автомата у с помощью операции инициальной обратной связи (см. рис. 8) для г-ого выхода и j-oгo входа, если выполняются следующие условия.

1) А' — А х. х А]-1×1 х. х Ап.

2) 0,' есть множество всех состояний автомата у. в которых г-тый выход не зависит от ^'-того входа.

3) Для любых ак Е Ак (1 < к < п) и д € О!

Ф'(<1, (¿-ъ • • •, о-з-ъ • • •, о")) = Ф (д, (аь ., Фг (ч, (аь • ¦ ¦, а&bdquo-)), ь • • •, ап)).

Поскольку автомат у 27-корректен для обратной связи, то ф' не выходит за рамки .

4) Для любых ак Е Ак {1 < к < п) и q Е Qf.

1, — • ¦, %-ъ Ц+и ¦ - -, о")) = (^1, • • •, ап)).

5) Для любых ак € Ак (1 < к < п), д € Я' и I ф г.

Ф’М, ., %-ь ., Оп)) = (аь • • ¦ > аз-ь ^?(<7, («1, • • •, ап)), %+1,., ап)).

Состояние автомата д называется достижимым, если существует такое, а е А*, что Ф (а) = д.

Будем говорить, что выход г автомата v зависит с задержкой от входам, если в каждом достижимом состояния автомата V ¿—тый выход не зависит от^-того входа.

Пусть в автомате V г-тый выход зависит с задержкой от ^'-того входа. Будем говорить, что автомат 9е[у^,]) получен из автомата v с помощью операции классической обратной связи для г-ого выхода и 7-ого входа, если.

9е (М,.7') = 8.

То есть инициальная обратная связь и классическая обратная связь есть одна и та же операция, отличаются они только областью определения. Классическая обратная связь определяется на множестве автоматов, у которых г-тый выход зависит с задержкой от ^'-того входа. Инициальная обратная связь определяется на ^/-корректных автоматах. Область определения инициальной обратной связи шире. Обычно в литературе, посвященной теории автоматов, рассматриваются классические обратные связи (поэтому они здесь и названы классическими). Однако при рассмотрении автоматных уравнений, чему посвящена данная работа, инициальные обратные связи оказываются намного естественнее. Забегая немного вперед скажем, что автоматные уравнения с одной неизвестной сначала решаются для инициальных обратных связей, а уже через этот результат — для классических.

В дальнейшем под операцией обратной связи (о. с.) мы будем подразумевать инициальную обратную связь.

Пусть VI = (Аи (21,В1,ф1,ф1,<$) и г>2 = (Л2, Я2, В2, Ф2, Я2) — БУДем говорить, что автомат у является декартовым произведением автоматов VI и и2, если V = (/Ц х А2, Я 1 х Я2, Вг х В2: фг х ф2, фх х (.