Оглавление
Введение 3
1. Общая характеристика работы ....................................... 3
2. Содержание работы.................................................. 4
3. Публикации по теме диссертации.................................... 17
4. Обзор литературы.................................................. 18
4.1 Обобщенная сеть (В.Б. Кудрявцев)............................ 18
4.2 Задача декомпозиции (А.К. Григорян)......................... 18
4.3 Структурные автоматные уравнения
(A.C. Подколзин, LLT.M. Ушчумлич)......................... 19
4.4 Автоматные уравнения для языков
(Н.В. Евтушенко и др.).................................... 22
1 Уравнение с одной неизвестной 24
1.1 Упрощение автоматного уравнения с одной неизвестной ... 24
1.2 Вложимость автоматов ............................................ 26
1.3 Алгоритм для определения вложи мости............................. 34
1.4 Уравнение с полной информацией................................... 38
1.5 Уравнение без обратной связи .................................... 41
1.6 Уравнение с инициальными обратными связями.................... 47
1.7 Уравнение с классическими обратными связями.................... 52
1.8 Свойства вложимых и редуцированных множеств...................... 59
2 Уравнение с двумя и более неизвестными 65
3 Решение во множестве детерминированных функций 76
3.1 Уравнение с одной неизвестной.......... 77
3.2 Уравнение с двумя и более неизвестными. 79
4 Список литературы 83
2
Введение
1. Общая характеристика работы
Вот уже несколько десятилетий происходит постоянный рост сложности интегральных схем. Путем синтеза из простейших элементов, таких как логические функции и задержки, создаются все более сложные системы, являющиеся по сути автоматными схемами. Современные интегральные схемы могут содержать миллиарды логических элементов. При этом на первый план выходит задача синтеза интегральной схемы. Когда известен автомат, который должна реализовать интегральная схема, и требуется этот автомат "собрать" из простейших элементов. В этой области могут оказаться полезными результаты работы, решающие задачу синтеза (построения) недостающего участка автоматных схем так, чтобы вся схема функционировала требуемым образом.
Рассматривается задача решения автоматных уравнений, которая заключается в следующем. Есть автоматная схема, некоторые автоматы которой можно заменять на другие автоматы. Требуется определить, можно ли произвести такую замен}', чтобы схема стала эквивалентна некоторому заранее заданному автомату.
В работе используются методы теории автоматов, теории графов и теории алгоритмов.
Задача была впервые поставлена в общем случае академиком В.Б. Кудрявцевым в [3]. Частный случай решаемой задачи был рассмотрен Л.К. Григоряном в |5| и [6]. В этих работах решаются автоматные уравнения с одной неизвестной для 4 видов схем. Позже A.C. Подколзин и Ш.М. Ушчумлич в [7) ввели понятие автоматного уравнения, отличное от понятия автоматного уравнения, рассматриваемого в этой работе, и описали алгоритм, перечисляющий все решения такого уравнения с одной неизвестной. Кроме того, Н.В. Евтушенко в своих работах [8| - [10] рассматривала автоматные уравнения для разных классов языков, в том число и для недетермини-
3
рованных автоматов и получила необходимое условие для недетерминированного автомата, чтобы он был решением уравнения.
В работе впервые решается задача нахождения всех решений произвольного автоматного уравнения для одного неизвестного. Впервые рассматриваются уравнения с более чем одной неизвестной. Доказывается неразрешимость пролемы существования решения уравнений с более чем одной неизвестной.
Результаты работы могут оказаться полезными для теории автоматов, а также могут быть использованы при проектировании интегральных схем.
1. Предложен алгоритм для решения автоматного уравнения с одной неизвестной.
2. Доказана алгоритмическая неразрешимость проблемы существования решения автоматных уравнений с двумя и более неизвестными.
Автор выражает благодарность профессору В.А. Буевичу за постановку задачи, профессору Э.Э. Гасанову и академику В.Б. Кудрявцеву за ценные замечания при написании этой работы.
2. Содержание работы
Алфавит {0,..., к — 1} будем обозначать Е^.
Пусть А - произвольный конечный алфавит. Обозначим А* множество всех слов, а А°° - множество всех сверхслов над данным алфавитом.
Пусть а, 6 £ А*, тогда \а\ будем обозначать длину слова а. а аЬ - конкатенация этих слов.
Функция / : А* —► И* называется детерминированной, если она удовлетворяет следующим условиям.
1) Если а £ А*, то |/(а)| = |а|.
2) Пусть а 1 = а(1)...а(А;) и = а'(1).. .а'(к), /(оц) = 6(1).. .Ь(к) и /(бк'г) = 6'(1).. .6'(/с). И пусть при всех з. 1 < 5 < к, если а(1) = а'(1), • • •, а(з) = а'(з), то 6(1) - 6'(1),..., 6(5) = 6'(5).
Детерминированная функция д : у\* —> В* называется частичной для детерминированной функции } : Аж —> В*, если существует такое 7 € /I*, что для любого слова а £ А* /(7а) = /(7Ж°0*
Детерминированная функция называется ограниченно-детерминированной, или о.-д. функцией, если она имеет конечное множество частичных функций.
Детерминированным автоматом (ДА, или просто автоматом) называется шестерка {А, С), В, ф, ф, д°). где:
4
A - конечный входной алфавит;
В - конечный выходной алфавит;
Q - конечное множество состояний;
ф : Q х А —> Q - функция переходов;
ф : Q х А—> В - функция выходов;
<7° € Q - начальное состояние.
В случае, когда /1 = А\ х Л2 х ... х Ап, будем говорить, что автомат имеет п входов и алфавит г-ого входа - /1*.
В случае, когда В = В\ х В2 х ... х Bmt будем говорить, что автомат имеет т выходов и алфавит г-ого выхода - Вг. При этом функция выходов ф : Q х А —> В разбивается на т функций выходов ф^ : Q х А —*■ Вг.
1 < г < т следующим образом. Если для некоторых, q £ Q и а € Л
ф{я, а) = (61,62,..., Ьт), то фг(д, а) = Ьг. То есть ф = ф1 х ф2 х ... х фт.
Множество автоматов с входным алфавитом А и выходным В обозначим Р(А,В).
Обозначим F множество всех таких автоматов, каждый вход и выход которого имеет алфавит Ек, где к - некоторое натуральное число, для каждого входа или выхода свое.
Пусть здесь и далее у = (A,Q, В,ф,ф,у°) - детерминированный автомат.
Обозначим Ф : А* —* Q функцию, возвращающую состояние Ф(а), в котором окажется автомат v, если на вход ему подать слово а. Более строго:
1) Ф(Л) = q°. где Л - пустое слово;
2) Ф(а(1)... а(п - 1 )а(п)) = </;(Ф(а(1)... а(п — 1)), а(п)).
Обозначим Ф* : А* —» Q* функцию, возвращающую последовательность состояний Ф*(ог), через которые проходит автомат у, если на вход ему подать слово а. Более строго:
1) Ф*(Л) = д°, где Л - пустое слово;
2) Ф*(а(1).. .а(п — 1)а(п)) = Ф*(а(1).. .а(п — 1))Ф(а(1).. .а(п)).
Обозначим Ф : А* —» В функцию, возвращающую последнюю букву
Ф(а), выданную на выходе автомата v, если на вход ему подать слово а. Более строго:
Ф(а(1).. .а(п — 1)а(тг)) = ^(Ф(а(1).. .а(п — 1)), а(гг)).
Обозначим Ф* : А* —* В* функцию, возвращающую выходную последовательность Ф*(а), выданную на выходе автомата v, если на вход ему подать слово а. Более строго:
5
1) Ф*(Л) = Л, где Л - пустое слово;
2) Ф*(а(1).. .а(п — 1)а(п)) = Ф*(а(1).. .а(п - 1))Ф(а(1).. .а(п)).
Функцию Ф* будем называть функцией автомата у.
В [4] доказывается, что функция любого автомат всегда является о.-д. функцией, и наоборот: для любой о.-д. функции существует автомат, функцией которого она является.
Два автомата называются эквивалентными, если их автоматные функции совпадают.
Определим некоторые элементарные операции над автоматами, с помощью которых будут строиться автоматные схемы:
Операцией добавления фиктивного входа (см. рис. 1) будем называть функцию, отображающую множество Р(А, В) во множество Р(А х А', В), такую что произвольный автомат V = (А, ф, В, ф^фуЦ0) переходит в автомат у' = (/1 х /1', С1 В, ф\ ф\ 4°), такой что для всех </ € <3, а € А и а' € А1 выполняется:
Ф'{д, (а,а')) = ф{(7, а); Ф'(д, (а,а')) = ф(д,а).
Таким образом, операция добавления фиктивного входа просто добавляет ещё один вход к автомату, при этом новый вход становится несущественным. Обозначается данная операция 1£.
Операцией изъятия выхода (см. рис. 2) будем называть функцию, отображающую множество Р(Л, В х В') во множество Р(Л, В), такую что произвольный автомат у = {А>С}, В\ х ... х Рт, #°) переходит в автомат V1 = {/1,(2, #1 х ... х #гп_1, </>,?//, 4°), такой что для всех ц е С), а 6 А и 1 < г < т — 1 выполняется:
Шя>а) = ф{(д, а).
Таким образом, операция изъятия выхода просто игнорирует последний выход автомата. Обозначается данная операция 2^.
Пусть Ап-\ = Ап. Операцией склеивания входов (см. рис. 3) будем называть функцию, отображающую множество Р(ЛХ х ... х Лп_х х /1П, В) во множество Р(А\ х ... х Лп_х,Р), такую что произвольный автомат и = (Лх х ... х Ап-1 х АП) С^,В,ф, ?/?, <7°) переходит в автомат у1 = (Лх х ... х Л„_х, ф\ ф\ ^°), такой что для всех <7 е <2 и а* € /1* выполняется:
Ф (<?> (^1> • • • > 0) = (аь •••! &п—ь &П—1));
ф'(д, (а1}..., ап_х)) = ф(д, (ах,..., ап_х, Оп-О).
6
- Київ+380960830922