Лупал А. М. - Теория автоматов

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

1. КИБЕРНЕТИКА - НАУКА ОБ УПРАВЛЕНИИ

1.1. Создание кибернетики

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

Впервые представление об искусственном интеллекте появилось в научно-фантастической литературе, в частности американский ученый и писатель Айзек Азимов в 1974 году писал: “Я придумал в 1942 году три закона робототехники и написал на их основе несколько десятков рассказов, относясь ко всем этим роботам и искусственным интеллектам как к экзотическим плодам воображения. Я считал, что робот (или вычислительная машина, или искусственный интеллект) необходим человечеству. Затем я обнаружил, что, в конце концов, вычислительные машины смогут достичь интеллектуального уровня, сравнимого с человеческим... и даже намного превзойти его..., но, тем не менее, я должен открыть Вам одно обстоятельство: я никогда не верил в реальность всего этого - в этом отношении мое воображение отказало. Я никогда в действительности не предполагал, что искусственный интеллект возможен, и я совершенно определенно никак не предполагал, что застану время, когда люди будут серьезно работать в этой области” [1].

Научная теория по разработке искусственного интеллекта была провозглашена американским ученым Норбертом Винером в 1948 году. Тогда же он ввел понятие “кибернетики” как науки об общих закономерностях процессов управления и передачи информации в машинах, живых организмах и их объединениях. Вместе с этим словом более 50 лет назад в наш мир ворвался целый поток совершенно новых идей и представлений.

В России первые работы по кибернетике появились в 1956 году, причем сначала это были в основном переводы книг и статей американских ученых, а спустя некоторое время появились и собственные разработки. Одними из первых русских кибернетиков были советские ученые Аксель Иванович Берг, Виктор Михайлович Глушков и Александр Андреевич Ляпунов.

1.2. Предмет и методы исследования кибернетики

В качестве основных разделов кибернетики могут быть выделены:

1. Теория информации, изучающая способы восприятия, хранения, преобразования и передачи информации.

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

3. Теория систем управления, которая изучает:

структуру и принципы построения систем управления, к которым относятся любые физические объекты, осуществляющие целенаправленную переработку информации, такие как нервная система животного, система автоматического управления движением самолета, электронная программно-управляемая вычислительная машина, система подразделений банка и т. п.;

процесс управления - понятие, которое определяет, каким требованиям должна удовлетворять последовательность действий (или ее описание), осуществляемых системой управления.

Кибернетика изучает абстрактные системы управления, которые представлены в виде математических схем (моделей). Основным свойством этих моделей является то, что они сохраняют информационные свойства соответствующих классов реальных систем, т. е. тех систем, которые моделируются с помощью этих моделей. В рамках кибернетики под влиянием запросов техники ЦВМ и управляющих вычислительных машин возникла специальная математическая дисциплина - теория автоматов, которая изучает специальный класс дискретных (цифровых) систем переработки информации, включающих в себя большое число элементов. Дискретные автоматы, изучаемые в теории автоматов, являются абстрактными моделями реальных систем как технических, так и биологических, которые перерабатывают цифровую информацию дискретными временными тактами.

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

Используемые в кибернетике методы исследования можно разделить на математические и экспериментальные, причем именно к последним относятся логический анализ и синтез систем управления. Поэтому дисциплины “Дискретная математика”, и “Теория автоматов” являются составными частями науки кибернетики.

2. ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ

2.1. Определение алгоритма

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

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

Алгоритм может быть определен как эффективная процедура, однозначно приводящая к результату. При разработке алгоритма необходимо формализовать процесс решения задачи, сведя его к применению конечной последовательности достаточно простых правил. Так, мы регулярно пользуемся алгоритмами выполнения основных арифметических операций над многозначными числами, разработанными еще в IX в. древневосточным математиком Аль-Хорезми (термин “алгоритм” произошел от имени этого ученого). До середины XIX в. все алгоритмы были вычислительными и имели дело, в основном, с числами. Поэтому все многообразие вычислений комбинировалось из 10-15 четко определенных операций арифметики, тригонометрии и анализа. Все было очевидно и не требовало специальных исследований.

Появление во второй половине XIX в. математики, имеющей дело с нечисловыми объектами (неэвклидова геометрия, теория групп, теория множеств) показало, что все не так просто и очевидно. Оказалось, что привычные рассуждения, применяемые к этим теориям, основанные на содержательном описании алгоритма, приводят к неразрешимым противоречиям (пример - так называемые противоречия теории множеств). Совершенно особым образом и крайне осторожно следует обращаться с таким понятием, как “бесконечность”. Были созданы так называемые финитные методы исследований, сущность которых заключается в том, что они допускают только конечные комплексы действий над конечным числом объектов. Все это потребовало уточнения понятия “алгоритм”.

2.2. Предмет теории алгоритмов

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

Поэтому предметом теории алгоритмов, решающей задачу уточнения понятия “алгоритм”, является в первую очередь уточнение таких понятий, как “объект”, который подвергается преобразованию и “действие”, совершаемое над этим объектом. Поэтому, разрабатывая алгоритм, необходимо предварительно выяснить:

какие объекты следует считать точно определенными;

какие элементарные действия над ними следует считать точно определенными;

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

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

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

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

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

2. Необходимо уточнить понятие “данные”, т. е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритм мог с ними работать. Для этого объекты должны быть четко определены и отличимы как друг от друга, так и от “необъектов”.

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

Наиболее распространенный тип алгоритмических данных - слова конечной длины в конечных алфавитах (например, числа), причем число символов в словах (длина слова) - естественная единица измерения обрабатываемой информации. Более сложный случай алгоритмических объектов - формулы. Они также являются словами конечной длины в данном конечном алфавите, однако не каждое слово есть формула.

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

4. Алгоритм должен быть дискретным, т. е. должен состоять из множества элементарных шагов или действий, причем множество различных шагов конечно. Примером множества элементарных действий является система команд ЭВМ.

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

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

В частности, всякий, кто предъявляет алгоритм решения некоторой задачи, например вычисления некоторой функции f(x), обязан показать, что алгоритм останавливается после конечного числа шагов (сходится) для любого х из области задания функции f

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

7. В процессе создания алгоритма следует различать понятия:

описание алгоритма (например, инструкцию или программу);

механизм реализации алгоритма (например, ЭВМ), который включает в себя средства управления ходом вычислений, а именно: средства пуска, средства остановки, средства реализации элементарных шагов, средства выдачи результатов, обеспечения детерминированности;

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

2.3. Блок-схемы алгоритмов, композиция алгоритмов

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

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

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

Например, блок-схема, вычисляющая функцию f=f₂(f_x(x)) , в которой в качестве аргумента используется другая функция и которая поэтому называется композицией функций, будет иметь вид, представленный на рис. 2.1.

А1 - алгоритм вычисления функци if (х), f (х)-

Рис. 2.1

В такой блок-схеме входные данные (входы) алгоритма А2 есть результаты (выходы) алгоритма АІ.Такое соединение алгоритмов называется композицией алгоритмов.

На блок-схеме алгоритма хорошо видна разница между описанием алгоритма и процессом его реализации. Описание - это граф, а процесс реализации - это пути в графе, которые определяются логическими условиями. Если в процессе реализации вычислений не появляется условий, ведущих к концу, и процесс зацикливается, это означает отсутствие сходимости алгоритма.

2.4. Алгоритмические модели

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

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

выбирается конечный набор исходных объектов, которые называются элементарными;

выбирается конечный набор способов построения из них новых объектов;

фиксируется набор элементарных шагов;

разрабатывается способ создания памяти и выборки информации из памяти.

В результате этих действий создается конкретная алгоритмическая модель.

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

1. В первой модели понятие алгоритма связывается с наиболее традиционными понятиями математики - вычислениями и числовыми функциями. Наиболее широко используемая модель этого типа - рекурсивные функции. Рекурсивная функция описывается посредством так называемых индуктивных (или рекуррентных) определений, основанных на переходе от n к n+1. Слово “рекуррентный” означает “возвратный” от латинского слова recurso - “возвращаюсь, бегу назад”. И если алгоритм носит возвратный характер, то он и называется рекурсивным. Примером может служить алгоритм получения натурального ряда чисел: чтобы определить число 4, нужно сначала определить число 3, а чтобы определить число 3, нужно сначала определить число 2 и т.д. вплоть до 1.

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

Оператором суперпозиции S^ называется подстановка в функцию от m переменных m функций от n одних и тех же переменных. Например, если имеем функции h(x₁, x₂, ...,x_m), g₁(x₁, x₂,..x_n), g₂(x₁, x₂, ...x_n), ...,

gjxv ^XV ...^{, x}n^{) , то S}mm ^(h gp g2^, ...^, gm⁾ = ^h(g1^(xP ^xV ...^{, x}n^), g2^(xP ^X2^, ...<sup>,

X</sup>n^), ...^, gm^(xV ^X2^, ...^,Xn⁾⁾ =A^X1^,xV ...^{, X}n⁾.

2. Второй тип алгоритмической модели основан на представлении об

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

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

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

3. МАШИНА ТЬЮРИНГА

В 1937 году английский математик А.М. Тьюринг, который был последователем теории о том, что машина способна мыслить и с ее помощью можно смоделировать психическую деятельность человека, предложил общую и вместе с тем очень простую концепцию вычислительной машины. В своем труде Тьюринг исходил из того, что предлагаемая им вычислительная машина уподобляется вычислителю, который выполняет операции в точном соответствии с некоторым строгим описанием. Работа машины Тьюринга напоминает действия вычислителя, который, будучи не в состоянии сразу обозреть всю, часто очень громоздкую систему данных и предписаний, производит каждый раз лишь какое-либо “элементарное” действие, причем только над некоторой “воспринимаемой” им частью данных (или промежуточных результатов). На следующем этапе он либо продолжает воспринимать ту же часть данных, либо переходит к другой части, находящейся рядом с ней.

3.1. Структура машины

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

1. Управляющее устройство (УУ), которое может быть настроено на выполнение одной из множества возможных операций или, как принято говорить, может находиться в одном из состояний, образующих конечное множество Q = {q₁, q₂, ..., q_n}.

Среди состояний УУ могут быть выделены начальное состояние q₁ и конечное (пассивное) состояние q_z с {q₁, ..., q_n}. В q₁ машина Тьюринга находится перед началом работы, а, попав в q_z, она останавливается. Очевидно, все состояния из множества Q, отличные от q_z, являются активными.

Работа машины Тьюринга происходит в дискретном времени, когда состояния машины рассматриваются на конечном множестве временных отсчетов, называемых тактами машинного времени и обозначаемых t₁, t₂, ..., t_p , ... .

2. Лента, разбитая на ячейки, в каждой из которых может быть записан один из символов конечного внешнего алфавита S = {s₁, s₂, ..., s_m}. Символами этого алфавита кодируются как сведения, подаваемые в машину, так и те сведения, которые в ней вырабатываются. Среди знаков внешнего алфавита имеется пустой символ (пробел) X. Посылка (вписывание) этого символа в какую-либо ячейку ленты гасит (стирает) тот символ, который в ней раньше хранился, и оставляет ее пустой. Следует заметить, что X может принимать значение из алфавита S.

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

3. Устройство обращения к ленте, представляющее собой считывающую и записывающую головку, которая в каждый момент времени t₍ обозревает какую-либо ячейку ленты и в зависимости от символа в этой ячейке и состояния УУ выполняет следующие действия (рис. 3.1):

а) производит или запись в ячейку нового символа (может быть совпадающего со старым), или стирание символа (запись в ячейку пустого символа X),

б) сдвигает головку на ячейку вправо или влево, при этом УУ переходит в новое состояние.

Перечисленные действия в комплексе представляют собой шаг (элементарное действие) машины Тьюринга, который определяется парой ⁽Ч_Р

лгч

. обозреваемая ячейка

головка

Рис. 3.1

Таким образом, сообразуясь с современными представлениями вычислительной техники, можно считать, что управляющее устройство и устройство обращения к ленте представляют собой Логический блок машины. Лента интерпретируется как внешняя память, в которой записываются исходные данные и окончательные результаты (данные - это слова, представленные в алфавите S). Внутренняя память машины Тьюринга может быть представлена в виде двух ячеек: ячейки сдвига D, в которую заносится знак (направление) сдвига, и ячейки состояния Q, отображающей текущее состояние машины. Элементарными шагами машины Тьюринга являются: считывание и запись символов, сдвиг головки на ячейку вправо или влево, или, иначе говоря, изменение адреса обозреваемой ячейки ленты на 1, переход УУ в новое состояние.

3.2. Детерминированность машины Тьюринга

Машина Тьюринга обладает свойством детерминированности, т. е. последовательность ее шагов определяется следующим образом.

Для любого внутреннего состояния q. и символа алфавита Sj однозначно задана логическая функция, которая определяет следующее состояние q'; символ s', который должен быть записан; направление сдвига головки d_k М {L, R, E}, где L - сдвиг влево, R - сдвиг вправо, Е -отсутствие сдвига; причем множество А = {L, R, E, q₁, ..., q_m} называется внутренним алфавитом машины Тьюринга.

Таким образом логическая функция машины Тьюринга сопоставляет каждой паре знаков (q_;, sj) тройку знаков (s', q', d_k) и может быть записана разными способами.

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

столбцов записана тройка символов q' s' d_k. (рис. 3.2).

qi q2 q-3 qr Si S2 qis1L S3 Sk

Рис. 3.2

Логическая функция может быть задана также с помощью системы Тьюрингов ых команд (Х_г), которые имеют вид

q . ^sj ^ q' s' ^dk^{, (1}

где знак “^” читается “влечет за собой” или “приводит к ...”. Команда, соответствующая фрагменту функциональной схемы, представленной на рис. 3.2, имеет вид q₂ s₂ ^ q₈ s₇ L .

Третьим способом задания логической функции является блок-схема, называемая диаграммой (графом) переходов и изображаемая в виде графа, в котором состояниям машины Тьюринга соответствуют вершины (узлы), а командам вида (1)- ребра, ведущие из q_{ в q', на которых записано Sj ^ s' d_k

На рис. 3.3 приведен фрагмент диаграммы переходов машины Тьюринга, соответствующий фрагменту функциональной схемы, представленной на рис. 3.2.

>s₇ L

Рис. 3.3

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

3.3. Работа машины Тьюринга

Рассмотрим работу машины Тьюринга на следующем примере.

Пусть задана машина Тьюринга с алфавитом S = {1, а, в, X] и состояниями Q ={q₁, q₂, q₃, q₄, q₅}.

Перед началом работы машины Тьюринга на ленту заносится начальная информация (например, пять единиц) и фиксируется начальная обозреваемая ячейка (например, 4-я), сдвиг отсутствует. Информация в этой ячейке отражает начальное состояние q₁ машины Тьюринга.

5 4 3 2 1

1 1 1 1 1

Логическая функция рассматриваемой машины описывается функциональной схемой (рис. 3.4).

q q2 q3 q4 q5 X q4 X R q3 X L qx X R q5 X L q5 X E 1 q2 a E qx p E q, 1 R q5 X R q51 E a q4 a L q2 a R q 1 l q4 X R q5 a E в q, p L q2p R q3 X L q41 R q5 p E

Рис. 3.4

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

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

Такт 1- ?!

В ячейки состояния Q и сдвига D заносятся значения начального состояния q₁ и начального сдвига Е и обозревается содержание начальной 4-й ячейки (символ “1”) при состоянии q₁. В соответствии с функциональной схемой результатом данного шага будет q₂ a E , т. е. выполняется Тьюрингова команда

q₁ 1 ^ q₂ a E ,

где q₂ указывает, на какую операцию перешли; a - что записали в обозреваемую ячейку; Е - направление сдвига головки.

Следовательно, сдвиг головки устройства обращения к ленте отсутствует, а символ “1” заменяется в 4-й ячейке на “a“.

Получим

5 4 3 2 1

1 a 1 1 1

т

Такт 2- ?2

Так как сдвига не было, то вновь обозревается 4-я ячейка, но уже в состоянии q₂.

Результат: q₂ a R, т. е. выполняется команда q₂ а ^ q₂ a R. Следовательно, головка передвинулась в 3-ю ячейку (вправо), в обозреваемой 4-й ячейке ленты остался символ а, а машина Тьюринга осталась в состоянии q₂. Получим

5 4 3 2 1

1

a

1

1

1

т

Такт 3- t₃

Обозревается “1” из 3-й ячейки. Результат: q₁ в E , т. е. выполняется команда q₂ 1 ^ q₁ в E , сдвига нет. Получим 5 4 3 2 1

1

a

в

1

1

т

Такт 4- t₄

Вновь анализируется 3-я ячейка в состоянии q₁ и обозревается символ в. Результат: q₁ в L , т. е. выполняется команда q₁ в ^ q₁ в L , и осуществляется сдвиг влево. Получим 5 4 3 2 1

1

a

в

1

1

т

Такт 5- t₅

Анализируется 4-я ячейка в состоянии q₁, обозревается символ а. Результат: q₄ a L, т. е. выполняется команда q₁ а ^ q₄ a L, осуществляется сдвиг головки влево. Получим 5 4 3 2 1

1

a

в

1

1

т

Такт 6- t₆

Обозревается 5-я ячейка в состоянии q₄. Там находится символ “1”, поэтому результат: q₅ X R , т. е. выполняется команда q₄ 1 ^ q₅ X R , и осуществляется сдвиг вправо. Получим

5 4 3 2 1

X а в 1 1

т

Такт 7- t₇

Обозревается 4-я ячейка в состоянии q₅. Там находится символ “а”, поэтому результат: q₅ а E, т. е. выполняется команда q₅ а ^ q₅ а E , состояние и символ не меняются, сдвига нет. Получим 5 4 3 2 1

X

а

в

1

1

т

Состояние q₅ является конечным состоянием машины Тьюринга или стоп-состоянием, так как после анализа символа а в состоянии q₅, никаких изменений на ленте не происходит и в новое состояние машина не перейдет.

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

В результате работы машины Тьюринга была получена следующая схема изменения информации на ленте.

	5	4	3	2	1
	1	1	1	1	1
	1	а	1	1	1
h	1	а	1	1	1
	1	а	в	1	1
	1	а	в	1	1
	1	а	в	1	1
		а	в	1	1
		а	в	1	1

Особенностью описания машины Тьюринга является то, что функциональная схема и структурная схема, ее реализующая, могут быть отождествлены, так как структурная схема всегда одинакова для любой машины. Таким образом, машины Тьюринга отличаются реализуемой логической функцией (Тьюринговой программой), которая существует или в виде функциональной схемы или в виде системы команд (Е_г). Поэтому термины “Функциональная схема МТ” и “Тьюрингова программа” являются синонимами.

Удобнее пользоваться упрощенной записью Тьюринговых команд и функциональных схем, в которых не записываются выходные символы алфавита и новые состояния, если они не меняются, а также не фиксируется знак Е, указывающий на отсутствие сдвига. Это позволяет в таблице опустить столбец, соответствующий стоп-состоянию, само стоп-состояние отметить знаком “ ! ”, а в системе команд нет необходимости фиксировать последнюю команду.

Например, вместо q2a^q2aR можно писать q2a^R. Тогда упрощенная функциональная схема, представленная на рис. 3.4, будет иметь вид, показанный на рис. 3.5.

q q q q X q R q L q R ! L 1 q а q P q R !X R а q L R 1L X R в L R 1R

Рис. 3.5

В таком представлении более нагляден факт того, что оказавшись в состоянии q₁ при обозреваемом знаке в, машина начинает серию сдвигов влево сквозь все рядом стоящие символы в, причем содержание обозреваемых ячеек не меняется (остается в), до тех пор пока в поле зрения головки не попадет какой-либо другой символ. Только при этих условиях машина Тьюринга выйдет из состояния q_v

3.4. Конфигурация машины Тьюринга

Конфигурацией (полным состоянием или машинным словом) машины Тьюринга называется совокупность ее следующих характеристик:

внутреннего состояния;

состояния ленты (т. е. слова, записанного на ленте);

положения головки на ленте.

Конфигурация обозначается тройкой символов K = a₁q_i a₂ , где q_t -текущее внутреннее состояние, a₁ - слово слева от головки; a₂ - слово, образованное символом, обозреваемым головкой, и символом справа от него, причем, слева от a₁ и справа от a₂ нет непустых символов (т. е. либо записано X, либо ничего).

Например, если внутреннее состояние q_t = abcde, а головка обозревает символ d, тогда конфигурация машины Тьюринга K = abcq_f de, т. е.

a

b

C

d

e

<-->

aj a2

Стандартная начальная конфигурация обозначается как K_l=q_la, где q₁ - начальное состояние, а головка обозревает крайний левый символ. Стандартная конечная конфигурация имеет вид Kz=q a, где q - конечное состояние и вокруг обозреваемой ячейки пустые символы.

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

Определение. Если к некоторой конфигурации машины Тьюринга K применима ровно одна команда, приводящая к конфигурации K’ , то говорят, что между конфигурациями K и K’ существует отношение K ^ K’ , что означает: K переходит в K’ по Тьюрингу.

Если же для K₁ и K_n существует последовательность различных конфигураций такая, что K₁ ^ K₂^ K₃ ^ ... ^ K_n, то такая последовательность обозначается K₁ K_n. Последовательность конфигураций K₁ ^ K₂^ ... ^ K_n однозначно определяется исходной конфигурацией K₁ и полностью описывает работу машины Тьюринга, начиная с K₁.

В качестве примера рассмотрим систему команд Е_т составленную на основе функциональной схемы, приведенной на рис. 3.4 (выписываем только те команды, которые понадобятся для иллюстрации):

q₁ 1 ^ q₂ a E (1) q₁ b ^ q₁ в L (4) q₄ 1 ^ q₅ X R (6)

q₂ a — q₂ a R (2) q. a — q₄ a L (5) q₅ a — q₅ a E (7)

q₂ 1 ^— q. ^{p E (3)}

При заданной входной информации (11111) и начальной ячейке (4-й) получим следующую последовательность конфигураций машины Тьюринга:

1q1 1111 —— 1q2a111—— 1a q2 111—— 1 aq 1 в 11——

-К1- -К2- -КЗ- -К4—

—— 1 q 1 ap 11—— q41 ap 11—— Aq ap11——Aq^apn —К5— —К6— —К7— —— ! —

стоп-состояние

Следовательно, 1q₁1111 ^ Aq₅ap11 .

3.5. Тьюрингово вычисление

Рассмотрим, как строится машина Тьюринга, реализующая некоторые простые алгоритмы.

Алгоритм операции “Сложение”.

Исходные данные и результаты операции сложения являются натуральными числами.

Считаем, что в машине Тьюринга каждое натуральное число задано в виде набора “1” и отделяется от другого числа символом “*”. Таким образом, алфавит машины Тьюринга будет S = {1,*Д}. Состояния заданы множеством Q = {q₀, q₁, q₂, q₃, q₄, q₅}.

Рассмотрим пример.

Начальные условия: в начальном состоянии q₀ на ленту машины Тьюринга подается пара чисел 6 и 4 и в поле зрения машины находится левая единица.

1

1

1

1

1

1

*

1

1

1

1

т Необходимо найти их сумму, т. е. записать подряд 10 единиц, получив

1 1 1 1 1 1 1 1 1 1

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

q q, q, 1 q2 X R L R X R qaR q,1 * !X L R

Рис. 3.6

Или использовать следующую систему команд (выписаны только те, которые понадобятся при создании последовательности конфигураций):

















Такт 1- ?1

q₀ 1 ^ q₂ X R, т. е. вместо первой “1” устанавливается пробел и в состоянии q₂ обозревается вторая “1”, так как сдвиг должен быть вправо.

Такт 2- ?2

q₂ 1 ^ R (записано в упрощенной форме), следовательно символ не меняется и состояние тоже, поэтому переходя направо от “1” к “1”, будем все время оставлять их в ячейках, оставаясь в состоянии q₂. Попав на знак “*”, его тоже оставим, так как q₂ * ^ R.

Этот сдвиг вправо будет продолжаться в течение 9 тактов до тех пор, пока в такте 11 не попадем в пустую ячейку.

Такты 1-10 (t₁ - t₁₀)

^ R

X i i i i i * i i i i

т т т ... т

Такт 11 - t_n

X

1

1

1

1

1

*

1

1

1

1

Такт 12 - t12 q2 X — q1 1, т. е. в пустую ячейку вписываем “1” и переходим в состояние q1

X 1 1 1 1 1 * 1 1 1 1 1

Теперь вновь попали в начальную ситуацию, но уже не в состоянии q₀, а в состоянии q₁.

Такт 13 - t₁₃ q1 1 —— L

^ L

X 1 1 1 1 1 * 1 1 1 1 1

^t22 ^21 ^20 ^18 ^17 ^14 ^13

Далее в течение тактов t₁₄ - t₂₃ будет происходить обратный сдвиг (влево) через все 1 и * до тех пор, пока головка не окажется в левой пустой ячейке.

Такт 23 - t₂₃

q₁ 1 — L, произвели последний сдвиг влево и оказались в пустой ячейке

X

1

1

1

1

1

*

1

1

1

1

1

Такт 24 - t₂₄

q₁ X — q₀ R, переходим в состояние q₀ и сдвигаемся вправо к первой

X 1 1 1 1 1 * 1 1 1 1

t24 (аналог t0)

Такт 25 - t25

X X 1 1 1 1 * 1 1 1 1 1

1₂₅ t₂₆ (аналог g

Т.е. цикл завершен, и с этого момента (t₂₆) начинается новый цикл аналогичных операций. По окончании этого цикла еще одна “1” будет перенесена слева направо в конец последовательности.

Такт 47 - t₄₇

X X 1 1 1 1 * 1 1 1 1 1 1

т т g Чі (аналог tn)

Такт 48 - t₄₈

X X 1 1 1 1 * 1 1 1 1 1 1

t48 (аналог t0) t35 (аналог t10)

Такт 49 - t₄₉ q₀1 ^ q₂ XR

X X X 1 1 1 * 1 1 1 1 1 1 1

t49 t50 (аналог t2) t

60 Предпоследний такт (t143)

X X X X X X * 1 1 1 1 1 1 1 1

Последний такт (t₁₄₄)

q₀ * ^ ! X, переходим в конечное состояние и помещаем пробел, вместо *

X

X

X

X

X

X

X

1

1

1

1

1

1

1

1

В результате получена нужная сумма.

^{ставлЯЮт Т}цикл

n - число символов после

Длительность выполнения операции “Сложение” зависит от величины слагаемых, так как временные затраты на один цикл сложения со-2 (m+n+1) тактов, где m - число символов перед “*”,

Полностью на выполнение сложения понадобится Т = 2 (m+n+1) m +2m = 2m (m+n+2) тактов

/ \ время на подготовку к циклу

число циклов и на завершение цикла.

Поэтому в нашем примере Т_цикл = 2-11 =22 (такта) и Т_слож = 12-12 = =144 (такта).

Временные соотношения иллюстрируются табл. 3.1

Таблица 3.1

Подготовка Цикл Завершение Начало Установка "1" (+10) (+11) t t і - t г t12 t23 t24 t25 - t26 t36 t47 t48 t49 - t50 t60 t71 t 72 t73 - t74 t84 t95 Чв t97 - t98 t108 t119 t120 t121 - t122 t132 t143-t144 (стоп-состояние)

I цикл -	^2 ^23	IV цикл -	?74 ?95
II цикл -	?26 - ?47	V цикл -	?98 - ?119
III цикл -	Ul o -Г*	VI цикл -	?122- W ?144- конец

3.6. Тезис Тьюринга

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

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

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

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

Исходя из тезиса Тьюринга, невозможность построения машины Тьюринга означает отсутствие алгоритма решения данной проблемы. Расшифруем это положение. В числе общих требований, предъявляемых к алгоритмам, упоминается требование результативности. Наиболее радикальной формулировкой здесь было бы требование, чтобы по любому алгоритму А и данным а можно было бы определить, приведет ли работа А при исходных данных а к результату или нет. Иначе говоря нужно построить алгоритм В, такой что В(А,а) = истина, если А(а) дает результат, и В(А,а) = ложъ, если А(а) не дает результата.

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

Построить машину Тьюринга Т₀ такую (с такой системой команд), что для любой машины Тьюринга Т с системой команд Е_т и любых исходных данных а для машины Т Т₀(Х_т, а) = истина, если Т(а) - останавливается и Т₀(Е_т, а) = ложъ, если Т(а) не останавливается (происходит зацикливание).

Эта задача называется проблемой остановки, и если остановка невозможна, т. е. решаемая проблема является алгоритмически неразрешимой, никакое кодирование системы команд Е_т и а в алфавите машины Т₀ не приводит к успеху.

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

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

4. ВВЕДЕНИЕ В ТЕОРИЮ АВТОМАТОВ

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

Можно выделить два основных аспекта работы автоматов.

1. Автоматы-распознаватели, которые распознают входные слова, т. е. отвечают на вопрос, принадлежит ли поданное на вход слово данному множеству.

2. Автоматы-преобразователи, которые преобразуют входные слова в выходные, т. е. реализуют автоматные отображения.

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

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

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

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

1. В исходном множестве фраз первого языка выделяются различные входящие в них элементы языка (корни слов, окончания, суффиксы, префиксы и т.п.). Эти элементы объединяются в алфавит, называемый входным.

2. Аналогичным образом из исходных фраз второго языка формируется выходной алфавит.

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

3. Перевод теперь представляется как установление соответствия между словами во входном и выходном алфавитах, что и делается на третьем этапе.

4. Используя алгоритм синтеза, по установленному соответствию строится осуществляющий его автомат А.

5. Используя алгоритм минимизации, производится оптимизация автомата А по числу состояний.

Полученный автомат будет осуществлять преобразование входных слов в выходные на более широкой области, включающей (при соблюдении оговоренных выше условий и соответствующих ограничений грамматики) все новые фразы, подлежащие переводу. Примером такого перевода было решение задачи перевода с венгерского языка на баскский, выполненное в Институте кибернетики в г. Киеве под руководством В.М. Глушкова. При ее решении по 10 парам исходных фраз был синтезирован автомат с 75 состояниями, который путем минимизации был приведен к 46 состояниям.

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

4.1. Алфавитные операторы и автоматы

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

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

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

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

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

Примером автомата с неединственным состоянием может служить устройство управления лифтом. Входными сигналами для него являются номера требуемых этажей ^Z1 < ^Z2 < ... < ^Zf < “. Реакция кабины лифта на каждый входной сигнал должна быть различной в зависимости от того, на какой этаж кабина приведена входными сигналами, поступившими к данному моменту времени. Если кабина находится ниже требуемого этажа она должна двигаться вверх до требуемого этажа, если выше - вниз до требуемого этажа, если на требуемом этаже -должна остаться на месте. Таким образом, выходные сигналы wуст-ройства управления лифтом можно считать равными разностям z. - z_k, где z_k - номер этажа, на котором находилась кабина лифта к моменту поступления очередного входного сигнала (номера требуемого этажа) z., при этом сигнал w. = 0 не включается в выходной алфавит (пустой символ). Появление каждого выходного сигнала зависит от входного сигнала, действующего в данный момент времени, и от номера этажа, на котором к этому моменту времени оказалась кабина лифта. По этой причине можно считать, что автомат управления лифтом имеет число состояний, равное числу этажей здания. Поскольку процесс движения кабины между этажами не представляет интереса, считается, что состояние автомата изменяется мгновенно в момент достижения кабиной очередного этажа и с этим же моментом времени отождествляется момент поступления входного сигнала, вызвавшего движение кабины к этому этажу.

4.2. Абстрактные автоматы

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

Абстрактный автомат работает в дискретном автоматном времени, последовательные моменты которого отождествляются с натуральными числами t = 1, 2, ... . В примере с лифтом моменты автоматного времени определяются кнопкой “пуск” либо моментами нажатия кнопок с номерами требуемых этажей.

Для задания абстрактного автомата нужно задать входной алфавит Z = {z₁, z₂, ..., z_p}, выходной алфавит W = {w₁, w₂, ..., w_G} и

множество A = {a₁, a₂, ..., a_M} его внутренних состояний, называемое просто множеством состоянии автомата. В каждый момент времени t = 0, 1, 2, ... абстрактный автомат A находится в некотором состоянии a_t = a(t) из A. Состояние a₀ = a(0) в начальный момент времени t = 0 называется начальным состоянием автомата A. Условно абстрактный автомат изображается в виде устройства (рис. 4.1) с одним входом и одним выходом.

Рис. 4.1

В каждый момент t автоматного времени, начиная c t = 1, на вход автомата поступает в качестве входного сигнала одна из букв z_t = z(t) алфавита Z. Конечные упорядоченные последовательности входных букв z(l)z(2)...z(k) автомата будут входными словами. На вход автомата может подаваться любое входное слово из некоторого фиксированного множества допустимых входных слов. Каждое допустимое слово p = z(l)z(2)...z(k), поданное на вход данного автомата А, вызывает появление на выходе автомата выходного слова q = w(1)w(2)...w(k), представляющего собой некоторую упорядоченную конечную последовательность выходных сигналов автомата A (букв алфавита W), имеющего ту же самую длину, что и соответствующее ему входное слово p. Получаемое преобразование ф_А допустимых входных слов p в соответствующие им выходные слова q является алфавитным оператором, индуцированным автоматом А, или просто оператором автомата А.

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

w(t) = z(t) - z(t-l),

если принять z(0) = z₁. Это и есть искомое преобразование входных слов автомата в выходные. Поскольку длина входных слов для этого преобразования не ограничена, множество допустимых входных слов для него бесконечно и даже несчетно при всяком F > 2.

Оператор ф_А однозначно определяется заданием функции переходов 5 и функции выходов X рассматриваемого автомата. Функция переходов определяет состояние a(t) автомата в некоторый момент t автоматного времени по входному сигналу z(t) в тот же самый момент и состояний a(t-l) в предыдущий момент автоматного времени

a(t) = 5(a(t-1), z(t)). (4.1)

Функция выходов определяет зависимость выходного сигнала от тех же самых переменных

w(t) = X(a(t-1), z(t)). (4.2)

Задавая любое выходное слово p = z(1)z(2)...z(k) и начальное состояние a(0) автомата, с помощью соотношений (4.1) и (4.2) можно последовательно определить все буквы соответствующего выходного слова

q = Ф_А(Р) = w(1)w(2)...w(k).

Таким образом, соотношения (4.1) и (4.2) действительно определяют оператор автомата A.

Функции переходов и выходов представляются обычно абстрактными частичными функциями 5(a, z) и X(a, z), задающими однозначное отображение некоторого множества пар (a, z)(aeA, zeZ) в множества A и W соответственно. Допустимыми входными словами для автомата A называют те и только те входные слова р, на которых с помощью функций 5 и X указанным выше способом можно определить соответствующие им выходные слова q = ф_A(p).

Автомат называют конечным, если конечны все три определяющие его множества Z, W, A.

Для примера с лифтом функции переходов и выходов определяются соответственно следующими равенствами:

a(t) = z(t), w(t) = z(t)-a(t-1).

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

Поскольку дальше будут рассматриваться только конечные автоматы, слово “конечный” будет опускаться.

Автомат называют вполне определенным, если его функции переходов и выходов заданы на всех парах (a, z), и частичным - в противном случае.

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

4.3. Способы задания абстрактных автоматов

Если заданы входной и выходной алфавиты автомата, а также множество его состояний, среди которых фиксировано начальное состояние a₀, для задания абстрактного автомата остается задать функцию переходов 5 функцию выходов A .

Автоматы, функции переходов и выходов которых удовлетворяют условиям (4.1), (4.2), называют автоматами Мили. Автоматы, у которых функции переходов и выходов удовлетворяют условиям

a(t) = 5(a(t-1), z(t)), (4.3)

называют автоматами Мура [2] .

Различие между автоматами Мили и Мура состоит в том, что выходной сигнал в автомате Мили зависит как от состояния в предыдущий момент времени, так и от входного сигнала в рассматриваемый момент времени, а в автомате Мура - только от состояния в рассматриваемый момент времени. Если подставить правую часть (4.3) в (4.4), то получится равенство типа (4.2). Таким образом, автомат Мура всегда можно свести к автомату Мили с тем же самым числом состояний и теми же самыми входным и выходным алфавитами. Для конечного автомата функции 5 и X определены на конечном множестве значений аргументов и принимают значения из конечных множеств. По этой причине для конечных автоматов функции 5 и X можно задать в виде таблиц.

Таблица 4.1 Таблица 4.2

a(t-1)	zo	Z1	Z2	a(t-1)	Zo	Z1	Z2
ao	a2	a3	a1	ao	w3	W2	W1
ai	a3	ao	a2	a1	w0	W3	wo
a2	ao	a1	a1	a2	w1	wo	W2
a3	a2	a2	a3	a3	W2	W1	W3

В табл. 4.1 и 4.2 приведены примеры соответственно функций переходов и выходов автомата Мили.

Поскольку области определения функций 5 и X совпадают, таблицы переходов и выходов могут быть совмещены в одну таблицу переходов-выходов (табл. 4.3), в которой на пересечении i-й строки иj-го столбца (ie {0, 1, 2, ..., n}, je {0, 1, 2, ..., г}) записывается в числителе новое состояние автомата, а в знаменателе - выходной сигнал, выработанный при переходе в это состояние.

В табл. 4.4, 4.5 приведены примеры функций переходов 5 и выходов X автомата Мура. Функция выходов X автомата Мура зависит только от одного параметра a(t), поэтому при совмещении таблиц переходов и выходов достаточно столбцу состояний автомата поставить в соответствие столбец выходных сигналов (табл. 4.6).

Таблица 4.3

a(t—1) zo Z1 Z2 ao a2 W3 a3 /W2 ai /W1 ai a3 /w0 ao /w3 a2 /W0 a2 ao /wi ai /wo ai /W2 a3 a2 /W2 a2 /W1 a3 /w3

Таблица 4.4

a(t-1) zo Zi Z2 ao a3 a2 ao ai ao a3 a2 a2 a2 ao ai a3 ao a2 a2 Таблица 4.6 w(t-1) a(t-i) zo zi Z2 W2 ao a3 a2 ao wo ai ao a3 a2 W3 a2 a2 ao ai W1 a3 ao a2 a2

Таблица 4.5

a(t) w(t) ai wo c.l W, a, w, i

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

z 0 I'M 0

z

Для автомата Мили вершины графа отмечаются состояниями. Если из состояния a. имеется переход в состояние а,, то из вершины a. в

I j I

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

Для автомата Мура вершины графа отмечаются состояниями и связанными с ними входными сигналами. Дуги графа отмечаются входными сигналами, под действием которых возникают рассматриваемые переходы.

В приведенных примерах функции 5 и X определены при всех значениях переменных a(t-1) и z(t), поэтому им соответствуют вполне определенные автоматы. Для частичных автоматов функции 5 и X определены не на всех парах a(t-1) и z(t). В этом случае на месте неопределенных переходов или выходов в таблицах ставятся прочерки. В графах же отсутствуют дуги, соответствующие неопределенным переходам, а вместо неопределенных выходных сигналов ставятся прочерки.

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

4.4. Автоматные операторы

Пусть оператор j_A автомата А удовлетворяет следующим четырем условиям.

1. ф_А осуществляет однозначное отображение (вообще говоря, частичное) множества входных слов в множество выходных слов.

2. Область определения оператора ф_А удовлетворяет условиям полноты, т. е. вместе с любым содержащимся в ней словом содержит и все начальные отрезки этого слова (так, если области определения оператора ф_А принадлежит слово z₁z₂z₃z₄, то ей принадлежат и слова z₁, z₁z₂, z₁z₂z₃). Пустое слово всегда входит в область определения оператора

Фа.

3. ф_А сохраняет длину слова: любое входное слово р, на котором оператор ф_А определен, имеет ту же длину, что и его образ ф_А(р). В частности, пустое слово переводится оператором ф_А в пустое слово.

4. ф_А переводит любой начальный отрезок слова р, на котором он определен, в имеющий ту же длину начальный отрезок слова ф_А(р).

Эти четыре условия называют условиями автоматности оператора, а удовлетворяющий им оператор - автоматным оператором.

Если алфавитный оператор ф удовлетворяет условиям автоматно-сти, можно построить автоматы Мили и Мура (вообще говоря, бесконечные), индуцирующие оператор ф. В случае, когда область определения оператора ф конечна (конечно множество слов, на которых определен оператор ф), эти автоматы также могут быть выбраны конечными [2] .

Не всякий алфавитный оператор удовлетворяет условиям автомат-ности. Существует, однако, прием, позволяющий превратить любой алфавитный оператор в автоматный оператор.

Пусть ф - произвольный алфавитный оператор с конечными входным Z и выходным W алфавитами, P - область определения этого оператора. Будем применять к оператору ф две операции. Первая из них называется операцией выравнивания длин слов. Она заключается в том, что во входной и выходной алфавиты добавляется по одной пустой букве а и в соответственно, а затем к любому слову p из P приписываются справа m_p экземпляров буквы а, а к его образу q = ф(р) приписываются слева n_q экземпляров буквы в так, чтобы длины полученных в результате приписывания этих букв слов p₁ и q₁ совпали. Если, в частности, числа m_p выбираются равными длине слова q, а числа n_q равными длине слова p, то операция выравнивания длины слов называется стандартной.

После выполнения операции выравнивания длин слов строится новый оператор ф₁, отображающий некоторое множество P₁ слов в алфавите Z и {а} в множество слов в алфавите W и {в}. Он действует по правилу q₁ = ф₁(р₁), где слова p₁ и q₁ получены выравниванием длин слов p и q, причем p пробегает все P. Оператор ф₁ называется при этом выравненным оператором.

Вторая операция применяется только к выравненным алфавитным операторам, т. е. к таким операторам, у которых длины входных и соответствующих им выходных слов равны между собой. Ее называют операцией пополнения. Она заключается в распространении отображения ф на начальные отрезки слов. Это осуществляется следующим образом. Если S - произвольный начальный отрезок любого слова p из области определения оператора ф, то ф(?) полагается равным начальному отрезку слова ф(р), имеющим ту же, что и отрезок S, длину.

В результате применения операции пополнения к произвольному выравненному алфавитному оператору ф₁ возникает оператор ф₁', называемый пополнением оператора ф₁. Если пополнение ф₁' оператора ф₁ является однозначным, то оно удовлетворяет, очевидно, всем четырем условиям автоматности. К сожалению, однако, в большинстве случаев пополнение оператора ф₁ неоднозначно. Вместе с тем справедливо следующее утверждение [2]: в случае, когда оператор ф₁ получен из некоторого однозначного алфавитного оператора в результате стандартной операции выравнивания длин слов, пополнение ф^ этого оператора однозначно и является автоматным оператором.

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

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

Для построенного таким методом оператора можно построить функции переходов и выходов.

5. АБСТРАКТНЫЙ СИНТЕЗ АВТОМАТОВ

5.1. Построение функций переходов и выходов по алфавитному оператору

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

Рассмотрим процесс построения функций переходов и выходов по алфавитному оператору на конкретном примере. Пусть входной и выходной алфавиты состоят только из двух букв {z₀, zj и {w₀, w₁} соответственно, а оператор (табл. 5.1) задан таблицей соответствия.

Таблица 5.1

z(1)	z(2)	z(3)	w(1)	w(2)	w(3)
z0	z0	z0	w1	w0	w0
z0	z0	z1	W0	w0	w0
z0	z1	z0	w1	w0	w0
z0	z1	z1	%	w1	w1
z1	z0	z0	W0	w0	w1
z1	z0	z1	W0	w1	w1
z1	z1	z0	W0	w1	w0
z1	z1	z1	w1	w0	w1

Данный оператор уже выравнен, так как длина каждого из входных слов равна длине соответствующего выходного слова. Каждому входному слову здесь сопоставляется не более одного выходного слова, поэтому оператор ф однозначен. Однако он не удовлетворяет второму условию автоматности. Действительно, если нумеровать слова в табл. 5.1 сверху вниз, то z(1) = z₀ для первого и третьего слов преобразуется в w(1) = w₁, а для второго и четвертого слов w₁(1) = w₀. По этой причине оператор ф неоднозначен для начальных отрезков слов. Устранить это можно было бы, приписав справа к каждому входному слову m_p = 3 экземпляра буквы а и слева к каждому выходному слову m_q = 3 экземпляра буквы в, т. е. применив стандартную процедуру выравнивания длин слов. Воспользуемся более экономной процедурой.

Поскольку в табл. 5.1 при z(1) = z₀ для второго и четвертого слов w(1) = w₀, а для первого и третьего слов w(1) = w₁, допишем справа к первым четырем входным словам а и слева к первым четырем, выходным словам в (табл. 5.2). Точно так же в табл. 5.1 при z(1) = z₁ для пятого, шестого и седьмого слов w(1) = w₀, а для восьмого слова w(1) = w₁, поэтому справа к пятому, шестому, седьмому и восьмому входным словам припишем букву а и слева к соответствующим выходным словам припишем букву р. Если при этом считать, что z(1) преобразуется в в, то для однобуквенных начальных отрезков слов получилось однозначное преобразование (см. табл. 5.2).

Таблица 5.2

z(1) z(2) z(3) z(4) W(1) w(2) w(3) w(4) z0 z0 z0 а P w1 w0 w0 z0 z0 z1 а P W0 W0 W0 z0 z1 z0 а P w1 W0 w0 z0 z1 z1 а P w0 w1 w1 z1 z0 z0 а P w0 w0 w1 z1 z0 z1 а P w0 w1 w1 z1 z1 z0 а P w0 w1 w0 z1 z1 z1 а P w1 w0 w1 Таблица 5.3 z(1) z(2) z(3) ¦(4) z(5) w(1) w(2) w(3) w(4) w(5) z0 z0 z0 а а р р w1 w0 w0 z0 z0 z1 а а р р w0 w0 w0 z0 z1 z0 а а р р w1 w0 w0 z0 z1 z1 а а р р w0 w1 w1 z1 z0 z0 а р w0 w0 w1 z1 z0 z1 а р w0 w1 w1 z1 z1 z0 а а р р w0 w1 w0 z1 z1 z1 а а р р w1 w0 w1

Рассмотрим двухбуквенные начальные отрезки входных слов. Они совпадают в парах входных слов (см. табл. 5.2). Поскольку комбинация z(1)z(2) = z_Qz_Q преобразуется неоднозначно, справа от первых двух входных слов дописываем букву а, а слева от первых двух выходных слов дописываем букву в (табл. 5.3). Точно так же поступаем со второй и четвертой парами входных и выходных слов. В третьей паре слов комбинация z(1)z(2) = z₁z₀ преобразуется однозначно (см. табл. 5.2) в w(1)w(2) = Pw_Q. По этой причине третью пару входных и выходных слов не изменяем (см. табл. 5.3). Трехбуквенные начальные отрезки входных слов в табл.

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

5.3 алфавитный оператор ф’, будет автоматным.

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

Построим теперь по табл. 5.3 графы автоматов Мили и Мура. Будем при этом предполагать, что последний символ каждого входного слова должен переводить автомат в начальное состояние. Начнем с графа автомата Мили (рис. 5.1).



В момент t = 0 автомат находится в состоянии a₀. При подаче в последующие моменты времени каждого входного сигнала z(t) автомат переходит в новое состояние и вырабатывает выходной сигнал w(t).

Поскольку для абстрактного автомата порядок нумерации состояний, отличных от a₀, безразличен, можно считать, что буква z(1) = z₀ первого входного слова из табл. 5.3 переводит автомат в состояние a₁. При этом вырабатывается выходной сигнал w(1) = р. Буква z(2) = z₀ переводит автомат из состояния a₁ в состояние a₂ и обеспечивает выработку выходного сигнала w(2) = р. Входная буква z(3) = z₀ переводит автомат из a₂ в a₃. Этому переходу соответствует выходной сигнал w(3) = w₁. Буквой z(4) = a автомат переводится в состояние a₄ с выдачей выходного сигнала w(4) = w₀. Последней во входном слове буквой z(5) = а автомат, согласно условию, должен переводиться в состояние a₀. Этому переходу соответствует выходной сигнал w(5) = w₀. Начальные отрезки z(1)z(2), w(1)w(2) второго входного и выходного слов совпадают с соответствующими начальными отрезками первого входного и выходного слов, поэтому первые два перехода для второго входного слова совпадают с уже построенными. Последующие переходы для этого слова строятся точно так же, как и для первого слова. Затем аналогичным образом строятся переходы для остальных входных и выходных слов (см. табл. 5.3).

Граф автомата Мура приведен на рис. 5.2. Он строится почти так же, как и для автомата Мили. Первое отличие состоит в том, что выходные сигналы записываются в вершинах, так как выходной сигнал автомата Мура в каждый момент времени определяется только состоянием и не зависит от входного сигнала.

а 0 а о а о а о а 0 а 0 а0 а 0

Второе отличие - в числе начальных состояний. Так как последняя буква каждого входного слова должна переводить автомат в начальное состояние, последняя буква каждого выходного слова соответствует начальному состоянию. Поскольку выходные слова в табл. 5.3 содержат две различные последние буквы w₀ и w₁, автомат должен иметь два равноправных начальных состояния а₀ и a^’, отмеченных выходными сигналами w₀ и w_l соответственно. Эти состояния должны быть равноправными в том смысле, что при z(1) = z₀ автомат из каждого из них переходит в состояние a₁, а при z(1) = z₁ автомат из каждого из них переходит в состояние a₁₂.

Автоматы, соответствующие рис. 5.1 и 5.2, имеют входной алфавит {z₀, z₁, a}. Так как из каждой вершины этих графов выходят дуги, отмеченные не более чем двумя из этих символов, рассматриваемые автоматы будут частичными.

По графам, изображенным на рис. 5.1 и 5.2, легко можно построить таблицы переходов и выходов автоматов.

5.2. Постановка задачи о синтезе автоматов

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

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

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

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

Два вполне определенных абстрактных автомата с общим входным и общим выходным алфавитами называют эквивалентными, если они имеют один и тот же алфавитный оператор.

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

Говорят, что частичный оператор ф продолжает частичный оператор у, если область определения оператора ф включает в себя область определения D оператора у, и на области D оба оператора совпадают. Частичный автомат B называют эквивалентным продолжением частичного автомата A, если оператор автомата В продолжает оператор автомата A.

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

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

Пусть табл. 5.4 и 5.5 задают функции переходов и выходов час

Таблица 5.6

a(t-1) z0 z a a a, a - a0 a a0 -

Таблица 5.5

a(t-1) zn z a wn wn - w1 «2 w1 -

a(t-1)	Z0	Z1
ao	a0	a1
a,	a	a
	2	0
a2	a0	a2

тичного автомата Таблица 5.4

Если при каком-либо переходе выходной сигнал не определен, то и состояние, в которое перейдет автомат, не имеет значения. Поэтому после внесения неопределенности из табл.5.5 в табл.5.4 получим табл.5.6. Соответствующий табл.5.4 и табл.5.5 граф автомата Мили приведен на рис. 5.3. На рис. 5.4 приведен граф автомата, соответствующий табл. 5.5 и 5.6.

z, /w 1

Z J /w J

Если исходным является автомат Мура, заданный в табл. 5.7, после внесения неопределенности в таблицу переходов, получим табл. 5.8.

Таблица 5.7 Таблица 5.8

w(t—1) a(t-1) zo z w(t-1) a(t-1) Z0 z1 w0 ao ao a1 W0 ao ao a1 w1 ai a2 ao w1 ai - ao - a2 ao a2 - «2 ao -

Табл.5.7 соответствует граф автомата, приведенный на рис.5.5, а табл. 5.8- граф автомата, приведенный на рис. 5.6.

z
Рис. 5.6

Вторым этапом минимизации является исключение недостижимых состоянии. Состояние а абстрактного (частичного или вполне определенного) автомата называется достижимым, если оно совпадает с начальным состоянием или если существует такое достижимое состояние b и такой входной сигнал z, что а = 5(b, z). В противном случае состояние а называется недостижимым. Автомат, все состояния которого достижимы, называется связным. Для получения связного автомата нужно вычеркнуть все строки таблиц переходов и выходов автомата, которые обозначены недостижимыми состояниями. Возможность уменьшения числа состояний на этом этапе увеличивается при увеличении степени неопределенности, внесенной в автомат на первом этапе.

Для автомата Мили, заданного табл. 5.4, 5.5 или рис. 5.3, все состояния достижимы, поэтому автомат, заданный табл. 5.4, 5.5 или рис. 5.3, будет связным. Для автомата, заданного табл. 5.5, 5.6 или рис. 5.4, состояние а₂ будет недостижимым, в силу чего автомат не будет связным.

Точно так же автомат Мура, заданный табл. 5.7 или рис. 5.5, является связным, а автомат, заданный табл. 5.8 или рис. 5.6, не будет связным, поскольку у него состояние а₂ недостижимо.

После вычеркивания в табл. 5.5, 5.6 и 5.8 строки, соответствующей состоянию а₂, получим связный автомат Мили, заданный табл. 5.9, 5.10 или рис. 5.7, и связный автомат Мура, заданный табл. 5.11 или рис. 5.8.

Таблица 5.9 Таблица 5.10 Таблица 5.11

a(t-1)	Z0	Z1	a(t-l)	zo	z1	w(t-l)	a(t-l)	zo	z,
ao	a0	a	ao	wo	wo	wo	ao	ao	a1
a	-	a0	ai	-	w1	w1	ai	-	ao

z 0 /'W
Рис. 5.7

Рис. 5.8

a a,

Zi/'w о

Третьим этапом минимизации автомата является объединение в одно состояние множества совместимых состояний.

5.3. Классы совместимости автомата

Пусть A - произвольный абстрактный автомат, a - любое его состояние. Говорят, что слово p во входном алфавите автомата A применимо к состоянию a, если, подавая это слово на вход автомата A, установленного предварительно в состояние а, мы получим на выходе определенное слово q в выходном алфавите, имеющее ту же самую длину, что слово р. Слово q называют результатом применения слова p к состоянию a.

Если слово р неприменимо к состоянию а, то результат применения слова р к состоянию а считается неопределенным (при этом безразлично, дают ли некоторые непустые начальные отрезки слова p в применении к состоянию а определенные результаты или нет).

Состояния а_г1, ..., а_ы, входящие в автомат Мили, называются совместимыми, если все определенные (не считая неопределенных результатов) результаты применения слова р к состояниям а_г1, ..., a_in будут одними и теми же (зависящими только от слова p, но не от выбора состояния а_к из данного множества состояний). Для автомата Мура, кроме этого условия, для совместимости данных состояний требуется, чтобы (не считая неопределенных отметок) все совместимые состояния имели бы одинаковые отметки. Совместимые состояния во вполне определенных автоматах называются также эквивалентными.

Для конечных автоматов существует конструктивный прием нахождения совместимых состоянии автомата Миля и Мура. Этот прием основан на использовании понятия /-совместимости состояний.

Состояния а_;1, ..., а_іп автомата Мили называются /-совместимыми для любого данного і = 1, 2, ..., если (с точностью до неопределенных результатов) результат применения любого слова длины i к состояниям а_/1, ..., а_п будет одним и тем же, находясь в зависимости лишь от выбо-

ра слова, но не от выбора состояния. Состояния автомата Мура называются 0-совместимыми, если (не считая неопределенных отметок) они одинаково отмечены; они называются /-совместимыми для любого i = 1, 2, ..., если они 0-совместимы и (с точностью до неопределенных результатов) результат применения любого данного слова длины i ко всем рассматриваемым состояниям одинаков.

Очевидно, /-совместимые состояния будут также и ф-совместимыми для любого j < i. Состояния тогда и только тогда совместимы, когда они /-совместимы для всех i =1, 2, ... . i-классом данного автомата Мили и Мура называется всякое максимальное множество i-совместимых между собой состояний автомата, т. е. такое множество, к которому нельзя добавить ни одного нового состояния без нарушения свойства i-совместимости. Всякое максимальное множество совместимых между собой состояний автомата называют финальным классом или классом совместимости автомата.

Непосредственно по таблицам выходов могут быть найдены 1-классы для автоматов Мили и 0-классы для автоматов Мура. В случае автомата Мили в один и тот же 1-класс зачисляются все состояния, одинаково обозначающие (с точностью до неопределенных выходных сигналов) строки таблиц выходов. В случае автомата Мура в один и тот же 0-класс зачисляются все одинаково отмеченные состояния и все состояния, отметки которых не определены (последние попадают, таким образом, во все 0-классы).

На этом примере видно, что для частичных автоматов i-классы, вообще говоря, пересекаются между собой. То же самое имеет место и для финальных классов. Для вполне определенных автоматов i-классы не могут пересекаться между собой.

Пусть K₁(i), ..., K_p(i) - совокупности всех i-классов автомата (Мили или Мура). Говорят, что тождество N состояний a_jl, ..., a_jk, целиком содержащееся в одном из i-классов K_r(i) выдерживает умножение на входную букву z_m, если все состояния b(a_j1, z_m), 6(a_j2, z_m), ..., 5(a_jk, z_m) (не считая тех, которые не определены) содержатся в одном и том же i-классе K(i), зависящем от выбора N и z_m е N.

Нахождение максимальных подмножеств состояний каждого i-класса, выдерживающих умножение на все буквы z₁, z₂, ..., z_F входного алфавита автомата называется операцией расщепления (разбиения) i-классов. Операция расщепления i-классов выполняются очевидным образом с помощью таблицы переходов рассматриваемого автомата.

В результате применения операции расщепления /-классов автомата Мили или Мура возникают все (/+1)-классы этого автомата (/ = 1, 2, ...). Ими является все максимальные множества, возникающие в результате расщепления.

Если применять последовательно операцию расщепления /-классов к конечному автомату Мили или Мура, отправляясь от 1-классов (для автомата Мили) или от 0-классов (для автомата Мура), то через конечное число шагов для некоторого k > 0 процесс расщепления k-классов даст в результате те же самые k-классы. Удовлетворяющие этому условию (нерасщепляемые далее) k-классы будут совпадать с финальными классами исходного автомата. Этот полученный В. М. Глушковым [2] результат является основой минимизации числа состояний конечных автоматов.

5.4. Автомат с минимальным числом состояний

Обозначим Ср c₂, ..., c_S финальные классы какого-либо автомата A с входным алфавитом Z = {z₁, z₂, ..., z_p}. Так как финальные классы являются вместе с тем и j-классами для всех j = 0, 1, 2, ..., то для каждой буквы z_k все состояния, входящие в любой финальный класс C_m, порождают один и тот же выходной сигнал (для автомата Мили) или отмечены одним и тем же выходным сигналом (для автомата Мура), либо соответствующие выходные сигналы не определены. Построим таблицу выходов некоторого автомата С, состояниями которого служат финальные классы c₁, с₂, ..., c_S, а входными сигналами - буквы алфавита Z. Для автомата Мили относим каждой паре (c_m, z_k) выходной сигнал, соответствующий паре (a_v, z_k) для любого an из класса c_m, для которого этот сигнал определен. Если же для всех пар (a_v, z_k) соответствующие им выходные сигналы не определены, то считаем, что выходной сигнал пары (c_m, z_k) также не определен. Для автомата Мура отмечаем каждый класс c_m выходным сигналом, которым отмечен произвольный элемент a_v е с_т. Если же все элементы, входящие в c_m не отмечены, то будем считать отметку класса c_m неопределенной.

Таблицу 5₁ переходов автомата C построим по следующему правилу: переход из c_m в 6₁(c_m, z_k) будет считаться неопределенным, если для состояний a_v, составляющих класс c_m, переход из a_v в 5(a_v, z_k) не определен. Если же хотя бы для одного состояния a_v е c_m переход из a_v в 5(a_v, z_k) определен, то переход из c_m в 5₁(c_m, z_k) также будет считаться определенным, а в качестве состояния 5₁(c_m, z_k) будет приниматься любой из финальных классов с. (их может быть несколько), содержащий все определенные состояния вида 8(a_v, z_k)(a_vec_m). Очевидно, финальные классы с. с требуемыми свойствами всегда существуют.

За начальное состояние автомата С можно принять любой финальный класс, содержащий начальное состояние автомата A, либо принять за начальные состояния автомата С некоторые или все финальные классы, содержащие начальное состояние автомата A.

Совокупность E всех финальных классов автомата A удовлетворяет условию полноты и условию замкнутости. Первое условие означает, что каждое состояние автомата A принадлежит какому-либо из финальных классов. Второе условие означает, что для каждой буквы входного алфавита все состояния каждого финального класса (с точностью до неопределенных переходов) переходят в состояния, принадлежащие одному финальному классу (тому же самому или другому). Пусть Е₀ - наименьшее подмножество E, удовлетворяющее условиям полноты и замкнутости. Условие замкнутости здесь означает, что для каждой буквы входного алфавита все состояния каждого финального класса из E₀ (с точностью до неопределенных переходов) переходят в состояния, принадлежащие одному (тому же самому или другому) финальному классу из E₀. Назовем минимальной нормальной формой автомата A нормальную форму, построенную по множеству финальных классов E₀.

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

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

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

5.5. Пример минимизации автомата Мили

Пусть частичный автомат Мили A задан графом, приведенным на рис. 5.1. Это связный автомат без неопределенных выходных сигналов. Его минимизацию будем осуществлять в два этапа. Сначала построим эквивалентный автомату A автомат B с меньшим чем у A числом состояний.

Согласно рис. 5.1, единственным применимым к состояниям a₄, a₆, a₉ и a₁₈ входным словом будет однобуквенное слово p = а с результатом применения q = w₀. По этой причине состояния a₄, a₆, a₉ и a₁₈ совместимы, и их можно заменить одним состоянием b₄. Точно так же убедимся в совместимости состояний a₁₁, a₁₄, a₁₅ и a₂₀, в силу чего их можно заменить одним состоянием b₇. Для состояний a₃, a₅, a₈ применимыми входными словами будут лишь двухбуквенное слово p₁= аа, которому соответствует результат применения q₁= w₀w₀, и однобуквенное слово p = а с результатом применения q = w₀. Следовательно, состояния a₃, a₅, a₈ совместимы, и их можно заменить одним состоянием b₃. Переобозначив теперь на рис. 5.1 a₀ на b₀, a₁ на b₁, a₂ на b₂, a₇ на b₅, a 10 на b₆, a₁₂ на b₈, a₁₃ на b^, a₁₆ на b₁₀, a₁₇ на b₁₁ и a_V9 на b₁₂, получим граф автомата Мили B, изображенный на рис. 5.9.

а/w 0
	b О b О

Автомат B имеет только 13 состояний вместо 21 состояния у автомата A. Эти автоматы эквивалентны. Действительно, пройдя все пути из состояния b₀ через другие состояния опять в b₀, убедимся в том, что оператор автомата B определен на всех входных словах из табл. 5.3 и на их начальных отрезках.

Других слов область определения оператора В не содержит. При этом каждому входному слову оператор автомата B сопоставляет то же самое единственное выходное слово, что и оператор автомата A.

Таблица 5.12

b(t-1)	a	zo	Zi
bo	-	b/P	b/e
bi	-	b/в	b/e
Ь2	-	b3/wi	b3/w0
b3	b4/W0	-	-
Ь4	b0w 0	-	-
Ь5	-	b3/W1	b6/w0
Ь6	b7/w1	-	-
b7	bo/wi	-	-
Ь8	-	b9/W0
b9	-	b7/W0	b7w i
bio	-	bii/wo	bi2/Wi
Ь11	b4/W1	-	-
bi2	b7/wo	-	-

Графу рис. 5.9 соответствует таблица переходов-выходов табл. 5.12 автомата B. Финальные классы этого автомата будем искать с помощью треугольной таблицы (табл. 5.13), которая строится следующим образом.

Строки обозначаются состояниями b₁, b₂, ..., b_h-1, а столбцы состояниями b₀, b₁, ..., b_{h 2}, где h - число состояний автомата. На пересечении г-й строки и j-го столбца записываются условия, при которых возможно совмещение состояний А и bj. Если состояния нельзя совместить ни при каких условиях, ставится знак X, если совмещаются безусловно, то знак ?. Клетки, соответствующие пересечениям строк и столбцов с одинаковыми индексами, не заполняются. Окончательное совмещение состояний определяется на основании анализа непротиворечивости условий, записанных в клетках. Для рассматриваемого примера треугольная таблица (табл. 5.13) строится следующим образом.

Согласно табл. 5.12, состояниям b₀ и b₁ для каждого входного сигнала соответствуют одинаковые выходные сигналы, поэтому состояния b₀ и b₁ можно совместить, если при каждом входном сигнале они переходят в совместимые состояния, т. е. если можно совместить состояние b₁ с b₂ и состояние b₈ с b₅. Эти условия и записываются в верхнюю клетку, соответствующую столбцу для b₀ (табл. 5.13). Поскольку для состояний b₀ и b₂ найдется входной сигнал, для которого (см. табл. 5.12) выдаются различные входные сигналы, эти состояния совместить невозможно, и соответствующая клетка табл. 5.13 отмечается символом х. Состояния b₀ и b₃ совмещаются безусловно, поскольку при каждом входном сигнале переход определен только для одного из них. В соответствующей клетке табл. 5.13 нужно поставить поэтому символ ?. Затем анализируются остальные пары состояний столбца табл. 5.13, отмеченного состоянием b₀, после чего точно так же анализируются пары состояний, соответствующие остальным столбцам, начиная с верхней строки в каждом столбце. В результате этого анализа все клетки табл. 5.13 окажутся заполненными символами х, ? или условиями, при которых возможно совмещение состояний, соответствующих клеткам. После этого начинается анализ условий, записанных в клетках табл. 5.13.

Состояния b₀ и b₁ можно совместить в том случае, если совместимы состояния b₁, b₂ и b₅, b₈. Но в клетке, соответствующей состояниям b₁, b₂, стоит знакх, поэтому совместить состояния b₀ и b₁ невозможно и в соответствующей им клетке ставится символ х. Аналогичным образом находим, что и в клетке, отмеченной состояниями b₂, b₄, нужно поставить знак х. В клетке, отмеченной состояниями b₀ и b₄, стоит символ ?, поэтому в клетке, отмеченной состояниями b₃ и b₄, так же нужно поставить ?. В результате после такого анализа клеток, в которых записаны условия совместимости, в каждой клетке табл. 5.13 будет стоять символ х или символ ?. По такой треугольной таблице можно найти финальные классы.

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

b

bb

b

X

X

b3

V

V

V

Ь4

V

V

V

\V.

Ь5

X

X

X

V

V

Ь6

V

V

V

X

X

V

b

V

V

V

X

X

V

V

b8

X

X

X

V

V

X

V

V

Ь9

X

X

X

V

V

X

V

V

X

bio

X

X

X

V

V

X

V

V

X

b7, b11 b b12

Ь11

V

V

V

X

X

V

bT

boVb4

V

V

V

Ь12

V

V

V

bT

V

V

X

X

V

V

V

X

bo

b1

b2

b3

b4

b5

b6

b7

b8

b9

b1o

b11

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

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

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

Для рассматриваемого автомата Мили (табл. 5.12) по табл. 5.13 находим следующие пары совместимых состояний:

(b0, b3),	(bV bз),	(b2, b3),	(b3, b4),	(b4, b5),	(b5,	b6),
(b0, b4),	(bv b4),	(b2, b4^	(b3, b5),	(b4, b8),	(b5,	b7),
(b0, b6),	(b1, Ьб),	(b2, b6),	(b3, b8),	(b4, b9),	(b5,	b11),
(b0, b7),	(b1, b7),	(b2, b7),	(b3, b9),	(b4, b10),	(b5,	b12),
(b0, b11),	(b1, b11),	(K b11),	(b3, b10),	(b4, b12),
(b0, b12),	(K b12),	(b2, b12),
(b6, b7),	(b7, b8),	(b8, b11),	(b9, b11),	(b10, b11),
(b6, b8),	(b7, b9),	(b8, b12),	(b9, b12),	(b10, b12).

^(b6, ^b9⁾, ^(b7, ^Ью⁾,

^(b6, ^bio⁾, ^(b7, ^bn⁾,

2. На основе полученного множества производится укрупнение групп совместимых состояний, в результате чего должна быть получена полная совокупность финальных классов, в каждом из которых все состояния совместимы между собой. Для уменьшения сложности этой процедуры возможно при формировании каждого очередного класса совместимых состояний не рассматривать состояния, уже вошедшие в какой-либо из сформированных классов. В частности, в рассматриваемом случае состояние b₀ совместимо с состояниями b₃ и b₄, причем состояние b₃ так же совместимо с состоянием b₄, следовательно, их можно включить в один финальный класс K₁. Состояние b₀ совместимо и с состоянием b₆, однако b₆ не совместимо с состоянием b₃ и не может входить в этот же финальный класс. Аналогичная ситуация обнаруживается при анализе совместимых с b₀ состояний b₇, b₁₁, b₁₂. Подобным же образом формируются и все остальные финальные классы. В результате будут получены следующие классы совместимых состояний:

^K1 = {^b0^, К ^b4^{} K}5 = ^{b8<sup>}

K</sup>2 = ^{bV ^b6^{, b}7^{} K}6 = ^{b9b ^K3 = ^{b2^{, Ь}11^{} K}7 = ^{b10^}.

^K4 = ^{b5, ^b12^},

3. Производится анализ полученных финальных классов на удовлетворение условиям полноты и замкнутости. Проверка условия полноты очевидна и не вызывает затруднений, а проверка условия замкнутости выполняется по таблице переходов-выходов для всех состояний автомата. Если какие-либо два состояния, входящие в один из выбранных финальных классов, переводятся некоторым входным сигналом в состояния, принадлежащие разным классам, то нужно выбрать новое решение и проверить его на замкнутость.

Для рассматриваемого автомата при проверке финальных классов на замкнутость оказывается, что принадлежащие классу К₂ состояния b₆ и b₇ сигналом а переводятся в состояния, принадлежащие разным классам (b₆ -а^ b₇ е К₁, а b₇ -а^ b₀ е К₂), т. е. условие замкнутости не выполняется. Следовательно, необходимо одно из этих состояний (например, b₇) перенести в другой класс, не нарушая при этом условие замкнутости. Таким классом может быть класс К₅. В результате будет получено окончательное множество финальных классов, совпадающих с состояниями минимизированного автомата C

^С0 = ^К1 = ^{b0, ^b3, ^b4^}, ^C3 = ^K4 = ^{b5, ^b12^}, ^C6 = ^K7 = ^{b10^}.

^C1 = ^К2 = ^{bl, ^b6^}, ^C4 = ^К5 = ^{b7, ^b8^},

^C0 = ^К3 = ^{b2, ^b11^}, ^C5 = ^К6 = ^{b9^}.

4. Строится таблица переходов-выходов минимизированной нормальной формы заданного автомата. Далее по этой таблице можно построить граф переходов минимизированного автомата. Состояния переходов и выходные сигналы в этом автомате определяются по переходам и выходным сигналам того состояния, которое наиболее полно определено.

Таблица 5.14

c(t-1)	a	z0	Z1
С0	c0 /w0	c1 /Р	C4 ft
C1	C4 /W1	C2 /Р	c3 /Р
С2	co /wi	c0 /w1	c0/w0
С3	C4 /W0	c0 /w1	c1 /w0
С4	co/wi	c /w0	C6 Q
C5	-	C4 /W0	C4 /W1
C6	-	C2 /W0	c /w1

В рассматриваемом примере получены таблица переходов-выходов минимизированного автомата (табл. 5.14) и граф переходов (рис. 5.10).

5.6. Пример минимизации автомата Мура

Пусть частичный автомат Мура A задан графом, представленным на рис. 5.2. Поскольку все состояния этого автомата достижимы, а выходные сигналы определены для всех состояний, отпадает необходимость исключать недостижимые состояния. Будем опять минимизировать автомат в два этапа. Сначала построим эквивалентный автомату A автомат B с меньшим числом состояний.

Согласно рис. 5.2, если автомат A установлен в любое из состояний a4, a₆, a₉, то единственным допустимым входным словом будет однобуквенное слово p = а, которому соответствует единственное однобуквенное слово p = 0. По этой причине состояния a₄, a₆, a₉ совместимы и их можно заменить одним состоянием b₄. Аналогичным образом находим, что совместимы состояния a₁₁ и a₁₅, a₁₄ и a₂₀.

Первую пару заменим состоянием b₈, вторую - состоянием b₁₃. Если автомат установлен в состояния a₃ и a₈, то допустимыми входными словами будут лишь двухбуквенное слово p₁= аа, которому соответствует выходное слово q₁= w₀w₀ и однобуквенное слово p = а, которому соответствует выходное слово q = w₀. Следовательно, состояния а₃ и а₈ совместимы, и их можно заменить одним состоянием. Пе-реобозначив теперь на рис. 5.2 a₀” на b₀”, a₀' на b₀', a₁ на b_x, a₂ на b₂, a₅ на b₅, a₇ на b₆, a 10 на b₇, a_n на b₈, a₁₂ на b₉, a₁₃ на b₁₀, a₁₆ на b_n, a₁₉ на b₁₂, a₂₀ на b₁₃, a₁₇ на b₁₄, a₁₈ на b₁₅, получим граф автомата Мура B, изображенный на рис. 5.11.

Автомат B имеет 17 состояний вместо 22 у автомата A и эти автоматы эквивалентны.

b b b b О

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

Графу рис. 5.11 соответствует отмеченная таблица переходов (табл. 5.15) автомата B. Финальные классы автомата B будем находить с помощью треугольной таблицы (табл. 5.16), которая заполняется так же, как и для автомата Мили. Финальные классы находятся из нее для автомата Мура по тем же правилам, что и автомата Мили.

w(t-1)	b(t-1)	a	Z0	Z1
W0	V	-	b1	b9
	V	-	b1	b9
e	b1	-	b2	b6
e	Ь2	-	b3	b5
W1	b3	b4	-	-
W0	Ь4	b0'	-	-
W0	Ь5	b4	-	-
e	Ь6	-	b3	b7
W0	b7	b8	-	-
W1	Ь8	b0"	-	-
e	b9	-	b10	b11
W0	b10	-	b13	b8
e	b11	-	b14	b12
W1	b12	b13	-	-
%	b13	b0"	-	-
W0	b14	b15	-	-
W1	b15	b0'	-	-

Из табл. 5.16 имеем следующие пары совместимых состояний:

(Ъ0, ь₄), Фо", ^ьз), (^b3, ^bi₅), (b₄, b₅), (b₅, ^bio),

(bo, ^b5⁾, ^(b" ^b8⁾’ ^(b4’ ^b10⁾’

(bo', b₇), (bo", bi₂),

^(bo', ^bi3⁾, ^(bo", ^bi5⁾,

(bo', b14),

^(b7, ^Ьш⁾, ^(Ьш, ^bi3⁾, ^(bi3’ ^bi4⁾.

^(b7, ^bi3⁾, ^(bio, ^bi4⁾,

После проведения укрупнения групп совместимых состояний получим финальные классы и соответствующие им состояния минимального автомата C.

^C0 = ^Ki = ^{bo'. ^b4’ ^b5^}’ ^C5 = ^K7 = ^{b8^}’

C/’ = ^K2 = W* ^b3’ ^bi5^^{? C}6 = ^K8 = {^b9}’

X

X

X

X

X

v- к к

X

V

X

X

V

X

X

X

X

V

X

X

X

X

V*

X

X

b2 b3 2x 3 b6 bl

b5 bl 5x 1

X

X

X

V

X

X

X

X

b.'xb,

V-

X

X

V

X

X

4b-

X

X

X

X

X

X

b2XU bA

xx bA

X

X

X

xx brK

X

X

b2’ b3 X 3 Kh

X

X

X

X

V

V

X

V

X

X

X

X

b2Xbl4 bAi

b3Xbi4 bVb,2

X

X

X

b3Xb14 b~1b, 2

X

X

VX b11 b12

X

X

V

X

X

b4b13

X

X

X

X

‘•X-

X

X

X

V

X

X

X

X

b.'xb.-

b'b

X

‘•Vb

X

X

V

X

X

V

X

X

X

X

b.Xb13

b*Xb 15

X

b-’X 15

X

X

V

X

X

b.'Vb15

X

V

X

X

v*

X

X

X

X

bT

X

X

X

‘•^13

X

X

Cl = K3 = {bj, c₇ = K₉ = {b_n},

^C2 = ^K4 = ^{b2^}, ^C8 = ^K10 = ^{b12^},

^C3 = ^K5 = ^{b6^{} C}9 = ^K11 = ^{b13’ ^b14<sup>}

C</sup>4 = ^K6 = ^{b1 ^b10^}

Полученное множество финальных классов удовлетворяет условиям полноты и замкнутости, в чем легко убедиться с помощью табл. 5.15. Для этого множества строим нормальную форму автомата, которая и будет минимальным автоматом эквивалентно продолжающим автомат A. Отмеченная таблица переходов минимального автомата приведена в табл. 5.17. По ней на рис. 5.12 построен граф минимального автомата Мура.

Таблица 5.17

w(t—1)	c(t-\)	a	zo	z
wn	c'	C'	c	c
		0	1
w1	c ” c0	Co'	c1	c6
в	c1	-	C2	C3
в	c2	-	c" Co	Co'
в	c3	-	c Co	c4
wn	c	c	c	c
			9
w1	C5	c" c0"	-	-
в	C6	-	C4	c7
в	C7	-	C9	c8
w1	C8	c9	-	-
WO	C9	c" c0"	-	-

С помощью табл. 5.3 легко убеждаемся в том, что все допустимые входные слова оператора автомата A и их начальные отрезки принадлежат области определения оператора минимального автомата. По рис. 5.12 находим, что входное слово p = z^^aaa принадлежит области определения оператора минимального автомата. Согласно табл. 5.3, это слово не принадлежит области определения оператора исходного автомата A. Таким образом, минимальный автомат эквивалентно продолжает заданный.

6. СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТОВ

6.1. Композиция автоматов

Структурный синтез автоматов осуществляется на базе структурной теории автоматов, в которой в отличие от абстрактной теории производится учет большого числа свойств реально существующих цифровых автоматов. Абстрактный автомат представляет собой математическую модель проектируемого устройства. В структурном же автомате учитывается структура входных и выходах сигналов, а также внутренняя структура автомата на уровне так называемых структурных схем. В структурной теории автоматов принят отсчет автоматного времени, начиная с 0 такта, т. е. t = 0, 1, 2, ...

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

Сформулируем определение общего способа композиции автоматов. Пусть {Aj, A2, ..., A_n}(n > 0) - конечное множество автоматов. Необходимо произвести объединение этих автоматов в систему совместно работающих автоматов. Введем некоторое конечное множество узлов, которые назовем внешними входными узлами, и некоторое конечное множество других узлов, которые назовем внешними выходными узлами. Входные и выходные узлы автоматов Aj, A₂, ..., A_n будем называть внутренними входными и выходными узлами.

Композиция автоматов состоит в том, что в полученной системе, состоящей из заданных автоматов Aj, A₂, ..., A_n и внешних узлов, производится отождествление некоторых узлов (как внешних, так и внутрен-

них). У цифровых автоматов операции отождествления узлов соответствует соединение этих узлов проводниками.

После проведения отождествления узлов произвольная система автоматов превращается в так называемую схему или сеть автоматов. Будем считать, что автоматы, входящие в схему, работают совместно, если в каждый момент t автоматного времени (t = 0, 1, 2, ...) на все внешние входные узлы схемы подается какой-либо набор элементарных сигналов (структурный входной сигнал), а со всех внешних выходных узлов схемы снимается полученный на них набор элементарных выходных сигналах (структурный выходной сигнал). Если в каждый момент дискретного времени t = 0, 1, 2,... структурный выходной сигнал схемы однозначно определяется поступившей к этому времени конечной последовательностью структурных входных сигналов, начальными состояниями, входящих в схему автоматов, и сделанными при построении схемы отождествлениями (соединениями) узлов, то построенная схема может рассматриваться как некоторый автомат А и называется структурной схемой этого автомата. Автомат А, полученный описанным способом, есть результат композиции автоматов A_x, A₂, ..., A .

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

в любой момент автоматного времени на каждый узел схемы (как внешний, так и внутренний) поступает какой-либо элементарный сигнал;

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

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

Неоднозначность элементарного сигнала в узле может появиться по двум причинам: к некоторому входному узлу подсоединено одновременно несколько выходных узлов, являющихся источниками элементарных сигналов, а также источником неоднозначности могут быть так называемые циклические цепи или петли структурных схем. Цепью называется последовательность автоматов, у каждого из которых один из выходных узлов соединен с входом последующего. Если выходной узел последнего автомата соединен со входным узлом первого, то такая цепь называется циклической или петлей (рис. 6.1).

Рис. 6.1

Если A_x, A₂, A3, A₄ - автоматы Мили, у которых выходной сигнал появляется одновременно со входным, то на входе автомата возникает неоднозначность элементарного сигнала, поскольку неизвестно, какой сигнал считать истинным - входной или поступивший по линии обратной связи. Автомат, построенный таким образом, называется некорректным. Некорректности можно избежать, если хотя бы один из входящих в петлю автоматов будет автоматом Мура, который реагирует на тот или иной входной сигнал выходным сигналом, возникающим на один такт автоматного времени позже, чем вызывавший его появление входной сигнал. Таким образом, для соблюдения второго условия корректности необходимо и достаточно, чтобы любой входной узел схемы соединялся не более, чем с одним внешним входным или внутренним выходным узлом схемы, и любая нетривиальная (содержащая не менее одного автомата) петля в схеме содержала бы в своем составе хотя бы один автомат Мура.

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

6.2. Канонический метод структурного синтеза автоматов

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

Одним из широко используемых методов структурного синтеза является так называемый канонический метод, теоретические основы которого были разработаны З.М. Глушковым, сформулировавшим и доказавшим теорему о структурной полноте [2].

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

Полнота системы переходов в автомате означает, что для любой пары состояний (a_;, aj) этого автомата найдется входной сигнал, переводящий один элемент этой пары в другой. Это положение справедливо, если i = j. Чтобы детерминированный автомат мог удовлетворять условию полноты переходов, число его входных сигналов должно быть не меньше числа состояний.

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



На основании теоремы о структурной полноте структурная схема всякого автомата А, синтезированного каноническим методом, будет состоять из двух частей: запоминающей части и комбинационной схемы (рис. 6.2). Запоминающая часть представляет собой совокупность элементарных автоматов Мура с полной системой переходов и выходов, а комбинационная часть представляет собой схему, построенную из логических элементов, составляющих функционально полный базис. Рассмотрим этапы структурного синтеза автомата каноническим методом.

1. Кодирование состояний абстрактного автомата. В процессе структурного синтеза различным состояниям заданного абстрактного автомата а. ставятся в соответствие различные упорядоченные последовательности состояний элементарных автоматов Q₁, Q₂, ..., Q_p. Этот процесс называется кодированием состояний автомата.

Результатом кодирования состояний является возникновение структурных состояний автомата Q^l = Q₁^l QR ... QR , где l = 0, 1, 2, ..., M (M+1) - число состояний абстрактного автомата. R = ]log₂(M+1)[ и ]b[ означает ближайшее целое число, большее b или равное ему, если b - целое. Эти состояния можно отождествить со структурными выходными сигналами запоминающей части автомата.

В связи с тем, что каждый структурный выходной сигнал памяти автомата представляет собой совокупность элементарных сигналов, поступающих по отдельным каналам, будем считать структурный выходной сигнал памяти векторным сигналом Q^l, в котором каждая компонента отождествляется с буквой структурного алфавита состоя^{ния Q} = ^Qv ...^{, Q}pb ^т. ^е. ^Q/^{е Q}.

2. Кодирование абстрактных входных и выходных сигналов. Абстрактным входным и выходным сигналами ze Z и w . е W, где Z и W- входной и выходной абстрактные алфавиты, ставятся в соответствие внешние структурные входные и выходные сигналы автомата, обозначаемые соответственно X = x2j ... x_L^j, и У = yRyR... y_N^k, где j = 1, 2, ..., F, F - число символов входного абстрактного алфавита, к = 1, 2, ..., G , G - число символов выходного абстрактного алфавита, L = ]log₂F[ и N = ]log₂G[. Сигналы x^j и у^к являются векторными сигналами, компоненты которых xj и yR - соответственно элементарные входные и выходные сигналы на каждом элементарном входном или выходном канале, т. е. xj е X = {x₁, x₂, ..., x_n}, а yRе Y = {y₁, y₂, ..., y_r}, - гдеХ и Y- соответственно структурные входной и выходной алфавиты.

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

QO+1) =5(Q(0, x(t)), y(t) = MQ(0, x(t))

(6.1)

и для структурного автомата Мура

Q(t+1) =5(Q(t), x(t)),

y(t) = ^(Q(t)). (6.2)

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

4. Формирование таблицы функций возбуждения структурного автомата. Из рис. 6.2 следует, что

q^(t) = Y^{(Q(t) x(t))}. ⁽⁶.3)

Сравнивая выражение (6.3) с функцией переходов структурного автомата (6.1) или (6.2) можно сделать вывод, что именно сигналом q(t) можно осуществить требуемые переходы при условии формирования некоторой функции y(Q, x), называемой функцией возбуждения автомата A , в соответствии с функцией переходов 5(Q, x). В дальнейшем для упрощения формулировок сигнал q(t) будем также называть функцией возбуждения автомата A. Отдельные компоненты вектора q(t) являются входными сигналами используемых элементарных автоматов.

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

5. Получение логических выражений функций возбуждения и выходных сигналов автоматов. Сигнал q(t) является структурным выходным сигналом комбинационной схемы автомата А, отличающейся тем, что ее структурный выходной сигнал получается путем преобразования структурного входного сигнала x(t) автомата А и структурного выходного сигнала Q(t) его памяти. Реализуя схему преобразования в виде композиции заданных логических элементов, можно осуществить все те переходы, которые предусматриваются функцией переходов автомата А. Аналогично формируется структурный выходной сигнал y(t) на выходе комбинационной схемы автомата А. Требуемые значения выходного сигнала обеспечиваются соответствующим синтезом этой схемы.

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

Как известно, по таблице истинности можно получить только совершенную дизъюнктивную и нормальную форму (СДНФ) заданной функции. Для того чтобы минимизировать функцию, целесообразно воспользоваться диаграммой Вейча.

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

Рассмотрим в качестве примера синтез структурной схемы автомата Мили, спроектированного в разделе 5, функции переходов которого описываются в табл. 5.14.

Обычно в качестве структурного алфавита используется двоичный структурный алфавит {0, 1}, а в качестве элементарного автомата используется автомат Мура с двумя состояниями.

Пусть имеем абстрактный элементарный автомат с входным алфавитом Г={?₁,?₂}, выходным алфавитом и алфавитом состояний С={с_рс₂} и таблицей переходов-выходов (табл. 6.1).

Таблица 6.1

Произведем операцию кодирования состояний, входных и выходных сигналов у элементарного и исходного автоматов. Поскольку структурный алфавит двоичный, число элементарных входных каналов автомата определяется как L > ]log₂F[, число элементарных выходных каналов определяется как N > ]log₂G[, а число элементов памяти автома-

та - как R > ]log₂(M+1)[.

Перейдем от абстрактного элементарного автомата к структурному. Закодируем абстрактные входные сигналы (табл. 6.2), выходные сигналы и состояния (табл. 6.3). Получим кодированную таблицу переходов-выходов элементарного автомата (табл. 6.4).

Таблица 6.2 Таблица 6.3 Таблица 6.4

V q С Q 0 1 V1 0 c1 0 0 0 1 V2 1 С2 1 1 1 0

Произведем также кодирование абстрактных входных сигналов (табл. 6.5), выходных сигналов (табл. 6.6) и состояний (табл. 6.7) заданного автомата, определив при этом число элементов памяти. Число элементарных входных каналов проектируемого структурного автомата L > ]log₂3[ = 2. Число его элементарных выходных каналов A^/>]log₂3[ = 2 и число элементов памяти R > ]log₂7[ = 3. Следовательно, схема проектируемого структурного автомата должна иметь вид, представленный на рис. 6.3. Определим структурный входной алфавит автомата (табл. 6.5), структурный выходной алфавит (табл. 6.6) и алфавит состояний (табл. 6.7). Разобьем таблицу переходов-выходов для данного абстрактного автомата (табл. 5.14) на две таблицы: таблицу переходов (табл. 6.8) и таблицу выходов (табл. 6.9).

Рис. 6.3

Таблица 6.6

Таблица 6.5

Таблица 6.7

z хі Х2 w Уі У2 c Qi Q2 Q3 z0 0 0 wo 0 0 С0 0 0 0 z1 0 1 w 0 1 С1 0 0 1 a 1 0 в 1 0 С2 0 1 0 С3 0 1 1 С4 1 0 0 На основании табл. 6.8 и 6 7 построим ко- с. 1 0 1 дированную таблицу переходов автомата С6 1 1 0

(табл. 6.10), а на основании табл. таблицу выходов (табл. 6.11).

Таблица 6.8

.6 и 6.9 построим кодированную

Таблица 6.9

ф-Х) a zi Z2 co Wo в в ci W1 в в C2 W1 Wi W0 c3 Wo Wi Wo C4 W1 Wo в C5 - Wo Wi C6 - Wo Wi Таблица 6.11 Qi Q2 Q3 XX X^ XX 10 00 01 000 00 10 10 0 0 1 01 10 10 0 1 0 01 01 00 0 1 1 00 01 00 1 0 0 01 00 10 1 0 1 - 00 01 1 1 0 _ 00 01

ф-Х)	a	Z1	Z2
С0	c0	C1	C4
ci	C4	C2	C3
С2	C0	co	co
С3	C4	co	C1
С4	co	C5	C6
C5	-	C4	C4
C6	-	C2	C3

Таблица 6.10

Qi Q2 Q3 XX2 10 00 01 0 0 0 000 001 100 0 0 1 100 010 011 0 1 0 000 000 000 0 1 1 100 000 001 1 0 0 000 101 110 1 0 1 - 100 100 1 1 0 — 010 011

В каждой клетке табл. 6.10 переходов записывается двоичный код соответствующего состояния автомата, а в каждой клетке табл. 6.11 выходов - двоичный код соответствующего выходного сигнала. Далее, пользуясь табл. 6.10 и 6.4, можно построить таблицу функций возбуждения структурного автомата (табл. 6.12), для чего в каждой клетке этой таблицы необходимо записать значения требуемых входных сигналов q₁, q₂ и q₃ для каждого из трех элементов памяти Q_p Q₂ и Q₃ в зависимости от фиксируемого в соответствующей клетке табл. 6.10 перехода из одного состояния в другое. Далее по табл. 6.11 и 6.12 сформируем логические выражения для функций возбуждения и выходного сигнала.

Чтобы получить минимальные ДНФ функций возбуждения q₁, q₂, q₃ и выходных сигналов Q₁, Q₂, Q₃, построим диаграммы Вейча для каждой из искомых функций. Аргументами всех функций возбуждения в соответствии с выражением (6.3) и табл. 6.12 являются состояния элементарных автоматов Q_p Q₂, Q₃ и входные сигналы Xj и x₂.

Таблица 6.12

Q Q Q XX XX2 XX2 10 00 01 0 0 0 000 001 100 0 0 1 101 011 010 0 1 0 010 010 010 0 1 1 111 011 010 1 0 0 100 001 010 1 0 1 - 001 001 1 1 0 - 100 101

Т. е.

4j = Yi^(Qi⁽t\ ^Q2⁽0, ^Q3^{(t) х}1⁽^ ^x2^(t))’

Ч2 = 72^(Q1^(t)’ ^Q2^{(t), Q}3^{(t) Х}1⁽0з ^X2^(t))’

?3 = 73^(Q1^(t)’ ^Q2^{(t) Q}3^{(t) X}1^(t), ^X2^(t)).

Аргументами для и у₂ в соответствии с выражением (6.1) и табл. 6.11 также являются Q₁, Q₂, Q₃, x₁ и x₂. Таким образом,

Y1^(t) = M^Q1^(t)’ ^Q2^{(t) Q}3^{(t) X}1^(t)’ ^X2^(t))’

Y2^(t) = ^2^(Q1^{(t) Q}2^{(t) Q}3^{(t) X}1^(t)’ ^X2^(t)).

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

^q1 ^X1^Q2^Q3 ^{V X}i^Q2^Q3 ^{V X}1^Q1^Q2^Q3 ^V Q\Ql

^q2 ^X1^Q1^Q3 ^{V X}2^Q1^Q2^Q3 ^{V QQ}2 ’

Ч3 = ^X2^Q1^Q3 ^{V X}2^Q1^Q3 ^{V X}2^Q1^Q2 ^{V X}1^X2^Q1^Q2 .

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

Логическое выражение для выходного сигнала у₂ целесообразно получать, минимизируя у₂ по “0”, а не по “1”, поскольку в этом случае получается выражение с меньший рангом. В результате имеем

У1 = ^X1^Q1^Q2 ^{V X}2^Q2^Q3 > ^у2 ^X2^Q1 ^{V X}1^Q2^Q3 ^{V X}1^X2^Q1 ^{V X}2^Q1^Q2 ^{V X}1^X2^Q2 ^V Q1Q2Q3 '

На базе полученных выражений можно построить структурную схему автомата в любом функционально полном базисе.

7. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ

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

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

A = {C, V, 5, X, cj,

где C = {cl, c2} - алфавит состояний; V = {v_p v₂, v₃, v₄} - входной алфавит, причем v₁ - сигнал, не меняющий исходное состояние автомата, такой, что c₁ = 5{c₁, v₁}, c₂= 5{c₂, v₁}; v₂ - сигнал, переводящий автомат в состояние, противоположное исходному, такой, что c₁ = 5{c₂, v₂}, c₂= 5{c₁, v₂}; v₃ - сигнал, всегда переводящий автомат в состояние c₁, такой, что c₁ = 5{c₁, v₃}, c₁ = 5{c₂, v₃}; v₄ - сигнал, всегда переводящий автомат в состояние v₄, такой, что c₂ = 5{c₁, v₄}, c₂ = 5{c₂, v₄}; c₁ -

начальное состояние; 5 и X - функция переходов и функция выходов, определяемые с помощью графа переходов (рис. 7.1).

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

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

Рис. 7.1

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

яний. Из автоматов с двумя входными сигналами только два из шести удовлетворяют приведенному требованию. Это автоматы, в которых в качестве входного алфавита используется алфавит V₁ = {v₃, v₄} (автомат А₁) и алфавит V₂ = {v_p v₂} (автомат A₂). Полным также является автомат А₃ с тремя входными сигналами с алфавитом V₃ = {v₁, v₃, v₄}, а также автомат А₄ с четырьмя входными сигналами.

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

Рассмотрим структурные особенности этих автоматов, считая, что любой структурный элементарный автомат с двумя состояниями имеет вид, представленный на рис. 7.2. Поскольку этот автомат является автоматом Мура, выходной сигнал задерживается относительно входного на один такт автоматного времени. В соответствии с теоремой о структурной полноте схему любого структурного элементарного автомата можно представить состоящей из двух частей: запоминающей части, в которой не производится логическое преобразование информации (элемент задержки сигнала t) и комбинационной схемы (рис. 7.3). Приведенная на рис. 7.3 функция возбуждения q (t) представляет собой собственную функцию возбуждения элемента памяти. Следует заметить, что для задания структурного элементарного автомата целесообразно использовать матрицу переходов, элементами которой являются значения структурных входных сигналов автомата, заданные на упорядоченных парах состояний структурного автомата и переводящие первый элемент соответствующей пары во второй.

Рис. 7.2 Рис. 7.3

Для рассматриваемой модели существует четыре возможных перехода структурных состояний: 0^0, 0^1, 1^0, 1^1. Для каждого из этих переходов найдется значение входного сигнала, вызывающего заданный переход. Тогда закон функционирования элементарного автомата, имеющего m элементарных входных каналов, можно описать следующей матрицей переходов:

Q(t)	Q(+1)		q	42	4k	4m
0 —	0			*00 •	¦ bk b00	.. bm b00
0	1	M =	*01	*o2i •	¦ bk • b01	• • bm b01
1 —	0		b10	*120 •	• bk •	¦ • bm b10
1	1		*0i	*121 •	• bk b11 •	¦ • bm b11

где Q(t) и Q(t+1) - состояния структурного элементарного автомата в последовательные моменты автоматного времени. Количество строк матрицы M для любого элементарного автомата с полной системой переходов равно четырем, а количество столбцов равно числу входных каналов.

Элемент матрицы b^kjj представляет собой значение входного сигнала q_k, под действием которого автомат переходит из состояния i в состояние j. При этом каждый элемент матрицы может быть равен 1, 0 или неопределенному коэффициенту b. Неопределенные коэффициенты записываются в том случае, когда значения сигналов, поступающих на данный вход, не влияют на рассматриваемый переход.

7.1. Элементарные автоматы с двумя входными сигналами

Для проведения операции структурного синтеза с целью получения структурной схемы элементарного автомата А_х, граф переходов которого приведен на рис. 7.4, необходимо провести операцию кодирования состояний автомата и его входных сигналов. Поскольку абстрактному автомату с двумя входными и двумя выходными сигналами соответствует структурный автомат с одним входным и одним выходным каналом, результат операции кодирования входных сигналов и состояний будет иметь вид, представленный соответственно в табл. 7.1 и 7.2.

	Таблица 7.1		Таблица 7.2
V	q	C	Q
V3	0	c	0
V4	1	C2	1

Рис. 7.6

На основании рис.7.4 и табл.7.1 и 7.2 можно составить кодированную таблицу переходов структурного элементарного автомата A_x (табл.7.3), кодированный граф переходов (рис. 7.5), а также его матрицу переходов

0

Рис.7.5

?з
?з
Рис.7.4

q(0

Q(+1)

q

0

1

0

1

(7.1)











Рассматривая табл. 7.3 и матрицу (7.1), можно заключить, что значение состояния автомата Q(t+1) и соответствующего ему выходного сигнала определяются значением входного сигнала q(t) и не зависят от состояния автомата Q(t), т. е. Q(t+1) = q(t). В то же время на основании анализа схемы, приведенной на рис. 7.3, можно сделать вывод, что

^Q(t+¹⁾ = q^XO.

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

q^(t) = q^/0

и комбинационная схема в таком случае становится для автомата А_х излишней.

Таким образом, схема автомата приобретает вид, представленный на рис. 7.6, а сам автомат А_х представляет собой элемент задержки и называется триггером типа D (delay - задержка).

Таблица 7.3

q 0 1 0 0 0 1 1 1

Рис.7.7

Перейдем к рассмотрению схемы структурного элементарного автомата A₂, граф переходов которого представлен на рис. 7.7. В процессе кодирования входных сигналов и состояний автомата можно сформировать соответственно табл. 7.4 и 7.2, из которых следует, что структурный автомат А₂ имеет так же, как и автомат А_р только один входной канал. На базе графа переходов автомата А₂ и табл. 7.4 и 7.2 получаем кодированный граф переходов (рис. 7.8), кодированную таблицу переходов (табл. 7.5) и матрицу переходов (7.2) автомата А₂.

Таблица 7.4 Таблица 7.5

V	q	q	0	1
V1	0	0	0	1
V2	1	1	1	0

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

^Q(t+¹⁾ = q⁽t⁾ Q ⁽t⁾ v q ⁽t^)Q(t⁾ = q⁽t⁾ © ^Q(t).

Поскольку в любом элементарном автомате

^Q(t+¹⁾ = qjt^

можно записать

q^O = q^(t) © ^Q(t).

Рис. 7.8

q(t) М2 T Q(t+1 qM)

Рис. 7.9

Следовательно, автомат А₂ может быть реализован на базе элемента задержки с добавлением комбинационной схемы, выполняющей операцию сложения по модулю 2, которая может быть построена в любом логическом базисе (рис. 7.9). Этот автомат называется триггером со счетным входом или триггером типа T.

7.2. Элементарные автоматы с тремя входными сигналами

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

Рассмотрим автомат A₃, использующий входной алфавит V₃ = {v_p v₃, v₄}, граф переходов которого представлен на рис. 7.10.

Таблица 7.6

V	q(0)	q(1)
V1	0	0
V2	1	0
V3	0	1

Рис. 7.10

Закодируем состояния автомата А₃ (табл. 7.2) и его входные сигналы. Поскольку автомат А₃ имеет три абстрактных входных сигнала, число его структурных входных каналов должно равняться двум и может быть закодировано способом, представленным в табл. 7.6. Комбинация структурных входных сигналов {1, 1} является запрещенной комбинацией для данного типа элементарного автомата. На основании табл. 7.2, 7.6 и рис. 7.10 построим кодированный граф переходов автомата А₃ (рис. 7.11), кодированную таблицу переходов (табл. 7.7) и матрицу переходов (7.3). Символ “b” в матрице переходов означает безразличное значение данного входного сигнала для указанного перехода. Прослеживая по табл. 7.7 переходы автомата А₃, можно убедиться, что единичное значение сигнала q⁽⁰⁾ переводит автомат в нулевое состояние независимо от значения его исходного состояния, и, наоборот, единичное значение сигнала q⁽¹⁾ переводит автомат всегда в единичное состояние. Благодаря этой особенности автомата A₃ его входные каналы называются соответственно нулевым ( q⁽⁰⁾) и единичным ( q⁽¹⁾ ).

(0)

(0)

Q(t)

о -

Q(t+1)

0

(7.3)

10 00 \ гл qm(t) t КС 1 с .. ж Q(t+r Т

Рис. 7.12

00

Рис. 7.11

яМ)

Логическое выражение для фикции q автомата А₃ можно получить из табл. 7.7, доопределив неопределенные переходы единицами. В результате получим

?эл(0 = Qt+1) = q ⁽⁰⁾(t)Q(t) V q⁽¹⁾(t).

Таблица 7.7

q(0) q(1) 0 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 - -

Переведя полученное выражение в базис Шеффера, получим qjt) = S(S(S(q⁽⁰⁾(t)), Q(t)), S(q⁽¹⁾(t)).

Можно получить другое выражение для q автомата А , доопределив запрещенные наборы не единицами, а нулями. В результате имеем

q эл(t) = q⁽⁰⁾(t) V q ⁽¹⁾(t) Q (t). (7.4)

Взяв отрицание от обеих частей выражения (7.4) и переведя его в базис Пирса, получим

qjf) = P(q⁽⁰⁾(t), P(q⁽¹⁾(t),Q(t))). (7.5)

Таким образом, комбинационная схема элементарного автомата представляет собой последовательное соединение либо элементов Пирса (для прямого значения входных сигналов), либо двух элементов Шеффера (для инверсного значения входных сигналов) и имеет два входных канала (рис. 7.12). Этот автомат получил название триггера с раздельными входами или триггера типа RS (set - установить; reset -сбросить), где с помощью R и S обозначены соответственно входы q⁽⁰⁾ и q⁽¹⁾.

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

Для построения различных модификаций RS-триггера в этом случае делается дублирование одного из трех абстрактных входных сигналов: Vp v₃ или v₄ и кодирование дополнительного сигнала структурными символами 11. Каждая полученная при этом разновидность триггера считается самостоятельным типом и имеет свое наименование.

Рассмотрим получаемые таким образом автоматы. Переходы, осуществляемые дополнительными сигналами v\, v’₃ или v’₄, показаны на графах переходов абстрактных автоматов А₄, А₅, A₆ соответственно на рис. 7.13, 7.14 и 7.15.

Рис. 7.15

Кодированные графы переходов, соответствующие приведенным абстрактным автоматам, имеют вид, представленный на рис. 7.16, 7.17 и

7.18.

Анализируя переходы автоматов на рис. 7.16, 7.17 и 7.18, можно заметить, что каждый дополнительный сигнал обеспечивает один из четырех возможных переходов. Автомат на рис. 7.16 под действием сигнала 11 остается в прежнем состоянии и называется триггером типа Е (іexclusive - исключительный, особенный), автомат на рис. 7.17 под действием сигнала 11 переходит в состояние 0 и называется триггером типа R, а автомат на рис. 7.18 переходит в состояние 1 и называется триггером типа S. Табл. 7.8 представляет собой общую кодированную таблицу переходов этих трех триггеров.

Таблица 7.8

R	S	^-триггер	R-триггер	S-триггер
0	1	0	1	0	1
0	0	0	1	0	1	0	1
0	1	1	1	1	1	1	1
1	0	0	0	0	0	0	0
1	1	0	1	0	0	1	1

Матрицы (7.4), (7.5) и (7.6) являются соответственно матрицами переходов триггеров E, R и S.

Рис. 7.18

R S

^b1 ^b2 0 1 1 0 ^b2 ^b1

(7.4)

Q(t)	Q(t+1)	R	S			R	S
0 —	0	b	b2			b	0
0	1 M =	0	1	(7.5)	M =	b	i
1 —	-0	i	b			i	0
1	1	0	b			b2	bi

В матрицах (7.4), (7.5) и (7.6) элементы могут принимать любые значения, кроме комбинации b₁ = 0 и b₂ = 1 одновременно, т. е. b ₁b₂ = 0.

Автомат А₄, представленный на рис. 7.13, может быть закодирован иначе, способом, предложенным в табл. 7.9. Тогда его кодированный граф переходов будет иметь вид, представленный на рис. 7.19, а таблица переходов - вид, представленный в табл. 7.10.

Таблица 7.9 Таблица 7.10

V	q(1)	q(2)	qi	q(2)	0	1
v1	0	0	0	0	0	i
V2	1	1	i	0	0	i
V3	1	0	0	i	0	0
v1'	0	1	i	i	i	i

Если сравнить таблицу переходов этого автомата с таблицей переходов триггера типа D (табл. 7.3), можно заметить, что при q(2)(t) = 1 состояния автомата Q(t+1) в табл. 7.10 так же, как и в табл. 7.3, определяются только значениями входного сигнала q(1)(t). В то же время при q(2)(t) = 0 автомат переходит в режим хранения информации (его состояния не меняются) независимо от смены сигналов на входе q(1)(t).

В связи с этим рассматриваемый автомат представляет собой модификацию D-триггера и называется триггером типа DV (valve - вентиль, клапан), где буквами D и V обозначены соответственно входы q(1) и q(2). Вход V является разрешающим входом по отношению ко входу D. Матрица переходов триггера типа DV имеет вид

Q(t) Q(t+1)

(7.9)









где элементы Ъ₁ и b₂ могут принимать любые значения, кроме комбинации Ъ₁ = Ъ₂=1, т. е. Ъ₁Ъ₂ = 0, а элементы Ъ₃ и Ъ₄ должны удовлетворять

условию b ₃Ъ₄ = 0, т. е. недопустимо, чтобы Ъ₃ = 0, а Ъ₄ = 1 одновременно.

Функция возбуждения DV-триггера имеет вид

qjt) = q(1)(t) q(2)(t) v q (2)(t) Q(t) = Q(t+1)

или иначе

Q(t+1) = D(t)V(t) v V(t)Q(t).

7.3. Элементарный автомат с четырьмя входными сигналами

Элементарный автомат А₇, граф переходов которого представлен на рис. 7.20, использует в качестве входного алфавита алфавит V₄ = {v₁, v₂, v₃, v₄}, содержащий все четыре абстрактных входных сигнала описываемой модели. Закодировав символы входного алфавита в соответствии с табл. 7.11, построим на основании рис. 7.20, табл. 7.2 и 7.11 кодированный граф переходов автомата (табл. 7.12) и матрицу переходов (7.10) этого автомата.

(0) q(1)

















0b

(7.10)

Таблица 7.11 Таблица 7.12

V q(1) q(2) qr> q2) 0 l V1 0 0 0 0 0 i V2 1 1 0 i l i V3 1 0 i 0 0 0 Vl' 0 1 i i i 0

Анализируя переходы автомата А₇ по табл. 7.12, приходим к заключению, что он функционирует одновременно как триггер RS (при нулевых и противоположных значениях входных сигналов) и как триггер Т (при q(0) = q(1) = 1). Поэтому автомат А₇ считается универсальным триггером типа JK, где входом J считается вход q(1), а входом K -

вход q(0).

Функция возбуждения триггера JK имеет вид

q_m(0 = q(1)(t) Q (t) v q (0)(t) Q(t) = Q(t+1)

или иначе

Q(t+1) = J(t) Q (t) v к (t)Q(t).

Структурная схема триггера реализуется обычно на базе триггера типа RS. В этом случае входы q(0)(t) и q(1)(t) RS-триггера будут иметь значения, определяемые следующими логическими выражениями:

q(0)Rs (t) = R(t) = K(t) Q(t), q(1)Rs (t) = S(t)=J(t) q (t).

Достаточно широкое применение в цифровых схемах находит элементарный автомат, полученный путем избыточного кодирования входных абстрактных сигналов автомата А₇, представленного в табл. 7.13.

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

Таблица 7.13 Таблица 7.14

V	q0)	q1	q(2)	q<0)	q(1)	q(2)	0	1
Vi	0	0	0	0	0	0	0	1
V2	0	0	1	0	0	1	1	1
V3	1	0	0	1	0	0	0	0
V4	0	1	0	0	1	0	1	0

На основании табл. 7.13 и 7.2 и рис. 7.20 получим кодированный граф переходов автомата (рис. 7.22), кодированную таблицу переходов (табл. 7.14) и матрицу переходов (7.11) этого автомата.

		000	000
		to	f''" 001 001		JJ
		100	100		4)10
			Рис. 7.22
Q(t)	Q(t+1)		q(0)	q(1)	q(2)
0 —	0		b	0	0
0	1	M =	0	bi	bi
1 —	0		b2	0	b2
1	1		0	b	0

(7.11)

Анализируя переходы автомата по табл. 7.14, можно заметить, что сигналы q(0) и q(1) работают аналогично сигналам R и S триггера типа RS, а сигнал q(2) изменяет состояние автомата на противоположное аналогично входному сигналу триггера Т. В связи с этим данный элемен-

q(1)

q(0)

— 1 1 — — — — — — 1 1 — 1

Рис. 7.23

q

тарный автомат получил название счетного триггера с раздельной установкой или триггера типа RST.

Логическое выражение для функции возбуждения этого триггера может быть получено на основании табл. 7.14 с помощью диаграммы Вей-ча (рис. 7.23) и будет иметь вид

Q(t+1) = qjt) = q(1)(t) V q (0>(t) q (2)(t)Q(t) V q(2)(t) Q (t). (7.12)

Или иначе Q(t+1) = S(t) V T(t) Q (t) V R (t) T (t)Q(t).

Структурная схема RST-триггера реализуется обычно на базе RS-триггера.

8. ТЕХНИЧЕСКАЯ РЕАЛИЗАЦИЯ ЭЛЕМЕНТАРНЫХ

АВТОМАТОВ

Для устойчивой работы автомата необходима его синхронизация и введение дополнительных схем (конъюнкторов) [5]. Обычно дополнительные схемы и входы синхронизирующих сигналов предусматриваются в самом элементе памяти при его технической реализации. На основе характеристического уравнения RS-триггера

Q(t+1) = S(S(S( R .„(О), Q(t)), S( S в_Х (t))) можно построить асинхронную схему этого триггера на элементах Шеффера с управлением по входам, представленную на рис. 8.1.





Рис. 8.1

Во избежание гонок [5] асинхронные триггеры обычно не используются в качестве элементов памяти в структурных автоматах. Подключая к входам асинхронного триггера схему управления, состоящую из логических элементов используемого базиса, можно получить синхронный (тактируемый) триггер. На рис. 8.2, а, б приведена схема синхронного RS-триггера и его логическая структура, в которых пунктиром обозначены побочные асинхронные входы. На рис. 8.2, в приведено условное изображение такого триггера. Входы S и R - информационные (входы функций возбуждения), а вход C - синхронизирующий (тактовый).

а) S

б) _ в) с

Рис. 8.2

Изменение состояния такого триггера может произойти только при

С = 1. Побочные входы S и R триггера предназначены для асинхронной установки триггера в состояние 0 и 1, минуя информационные и тактирующий входы. Функционирование в этом случае соответствует асинхронному RS-триггеру с инверсным управлением. При синхронной работе на побочных входах должна поддерживаться нейтральная комбинация сигналов ( S = R = 1).

Помимо синхронизации для устранения гонок в автоматах используется двойная память. В этом случае все элементы памяти структурного автомата должны быть организованы в виде двухтактных (двухступенчатых) схем. Они строятся на основе двух синхронных триггеров, соединенных последовательно. Синхронизирующие сигналы поступают на эти триггеры в соответствии с условиями организации таких сигналов в схемах с двойной памятью: на вход C первого триггера поступает прямой сигнал, а на вход C второго триггера - инверсный. Двухтактная схема RS-триггера, ее логическая структура и условное изображение приведены соответственно на рис. 8.3, а, б и в.



Первый триггер в двухтактной схеме называется ведущим M, а второй - ведомым S (М - master (хозяин), S - slave (невольник)).

Поскольку .RS-триггер устойчив по отношение к длительности входного сигнала, на его основе целесообразно строить различные варианты схем элементарных автоматов. Рассмотрим реализацию триггеров различных типов на основе синхронного RS-триггера.

На рис. 8.4 приведены схемы S- и R-триггеров, функционирующих в соответствии с табл. 7.8.



Функциональные схемы S-триггера и R-триггера одинаковы и конкретный тип триггера определяется наименованием входных и выходных каналов. На рис. 8.4 обозначения входов триггера без скобок соответствуют триггеру типа S, а обозначения в скобках - триггеру типа R.

На рис. 8.5 приведена функциональная схема R-триггера, работающего в соответствии с табл. 7.8.



В этой схеме при одновременном сочетании на входах S = R = 1 обеспечивается режим хранения информации и состояние триггера не меняется.

Рассмотрим техническую реализацию триггеров типа D, DV, T, JK, синтезируя их каноническим методом структурного синтеза, используя в качестве элемента памяти триггер типа RS.

Структурная схема любого триггера на базе триггера типа RS имеет вид, представленный на рис. 8.6.

Q память KC X (RS- триггер) R _ J

Рис. 8.6

1. Синтез триггеров типа D и DV. D-триггер осуществляет переходы из одного структурного состояния в другое в соответствии с кодированной таблицей переходов 8.1 На основе табл. 8.1 и матрицы переходов RS-триггера (7.3) можно составить кодированную таблицу функции возбуждения D-триггера (табл. 8.2).

Таблица 8.1 Таблица 8.2

	0	1	D	0	1
0	0	0	R	S	R	S
1	1	1	0	b	0	1	0
			1	0	1	0	b

Из табл. 8.2 можно с помощью диаграммы Вейча (рис. 8.7) найти логическое выражение для функции возбуждения R и с помощью другой диаграммы Вейча (рис. 8.8) - для функции возбуждения S.

R = D и S = D.

0 1 b

Рис. 8.8

b 1 0 0

D -- Рис. 8.7

D

Таким образом, функциональная схема D-триггера на основе RS-триггера должна состоять из RS-триггера с дополнительным инвертором на входе R. Логическая структура такого D-триггера и его условное обозначение приведены на рис. 8.9, а и б.

	'S а	TT
	D
	C
	>Яа

TT

1 С-

Рис. 8.9

Поскольку DV-триггер представляет собой модификацию D-триггера, его схему можно получить преобразованием последнего путем добавлением входа V, который должен быть логически связан операцией И с управляющим входом C (рис. 8.10).

2. Синтез триггера типа Т. Функционирование Г-триггера задается кодированной таблицей переходов (табл. 8.3).

Таблица 8.3 Таблица 8.4

	1	0	T	1	0
0	1	0	R	S	R	S
1	0	1	0	0	b	b	0
			1	1	0	0	0

Пользуясь матрицей переходов ^5-триггера (7.3) и табл. 8.3, составим кодированную таблицу функций возбуждения Г-триггера (табл. 8.4). Из табл. 8.3 можно с помощью диаграммы Вейча (рис. 8.11) найти логическое выражение для функции возбуждения R и с помощью другой диаграммы Вейча (рис. 8.12) - для функции возбуждения 5. Получим R = rQ и 5 = rQ , откуда R = rQ и 5 = rQ . В соответствии с этими выражениями схема асинхронного Г-триггера будет иметь вид, представленный на рис. 8.13, а. На рис. 8.13, б представлено условное обозначение асинхронного Г-триггера. Вместо схемы задержки для обеспечения устойчивой работы Г-триггера можно использовать двухступенчатую схему (рис. 8.14, а).

' S а TT C D V 1 ( 1- C 'Яа	Q Q
Рис. 8.10

b 1

Рис. 8.11

1 b

Рис. 8.12

Рис. 8.13

Рис. 8.14

В этой схеме синхронизирующий сигнал C , подаваемый на второй триггер, образуется конъюнкцией z_x и z₂ (zj&z₂), которая равна 1, если С = 0, и первый триггер не перебрасывается. Тогда в этот момент во второй триггер происходит перенос информации.

Условное обозначение двухтактного Г-триггера приведено на рис. 8.14, б.

3. Синтез триггера типа JK. Работа JK-триггера задается кодированной таблицей переходов (табл. 8.5).

Пользуясь матрицей переходов RS-триггера (7.3) и табл. 8.5, составим кодированную таблицу функций возбуждения JK-триггера (табл. 8.6).

Из табл. 8.6 с помощью диаграммы Вейча (рис. 8.15) можно найти логическое выражение для функции возбуждения S и с помощью другой диаграммы (рис. 8.16) - для функции возбуждения R.

Таблица 8.5

1 0 00 0 1 01 1 1 10 0 0 11 1 0

Таблица 8.6

KJ 0 1 R S R S 00 b 0 0 b 01 0 1 0 b 10 b 0 1 0 11 0 1 1 0

J K

b b 1 1

Рис. 8.16

1 1 b b

Рис. 8.15

Получим S = JQ и R = KQ, откуда S = JQ и R = KQ.

В соответствии с этими выражениями схема асинхронного JK-триггера будет иметь вид, представленный на рис. 8.17, а. На рис. 8.17, б представлено условное изображение асинхронного JK-триггера.

б)



-О J к

Рис. 8.17

На практике описанный триггер не применяется из-за сложности изготовления и жестких требований к длительности входных сигналов. Так же, как и в случае Т-триггера, проблема устойчивости эффективно решается в триггерах с двухступенчатым управлением. Функциональная схема двухступенчатого JK-триггера показана на рис. 8.18, а, его условное обозначение - на рис. 8.18, б.

а)



От двухступенчатого RS-триггера (рис. 8.3) она отличается наличием обратной связи с выходов Q и Q на входы элементов 1 и 2.

Следует заметить, что асинхронная установка любого двухступенчатого триггера в единичное и нулевое состояние (выходы R и S _а) производится импульсами логического 0. Состояния остальных входов

при асинхронном управлении безразличны. Когда входы R и S неза-действованы, на них следует поддерживать уровень логической 1.

S — 'Л T T T j T J TT C C C C K K R 'Ж,

Рис. 8.19 Рис. 8.20

На основе JK-триггера путем несложной коммутации входных каналов можно получить схемы триггеров типа RST (рис. 8.19) и типа T (рис. 8.20).

9. МИНИМИЗАЦИЯ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ

АВТОМАТОВ

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

Два состояния автомата a_m и а, называются эквивалентными (a_m= a_s), если k(a_m, = X(a_s, для всевозможных входных слов ^. Если а_т и a_s не эквивалентны, они различимы. Более слабой эквивалентностью яв-

к

ляется ^-эквивалентность. Состояния а и а ^-эквивалентны (а = а ) если k(a_m, ^_к) = k(a_s ^_к) для всевозможных входных слов Ъ,_к длины к. Если состояния k-эквивалентны, они к-различимы.

Введенные отношения эквивалентности и к-эквивалентности рефлексивны, симметричны и транзитивны, следовательно, они являются отношениями эквивалентности, а потому могут быть использованы для разбиения множества А состояний автомата на попарно не пересекающиеся классы (классы эквивалентности). Соответствующие разбиения на классы эквивалентных и k-эквивалентных состояний будем обозначать П и П_к. Разбиение П позволяет определить избыточные элементы в множестве состояний А. Пусть, например, a_m и a_s эквивалентны. Это значит, что с точки зрения реакций автомата на всевозможные входные слова неважно, находится автомат в состоянии a_m или a_s, и одно из них, например a, может быть удалено из множества A. Если каждый класс эквивалентности содержит только одно состояние, множество A несократимо. Если же один или несколько классов содержат более одного элемента, все элементы, кроме одного в каждом классе могут быть исключены из множества A , в результате чего получается автомат с минимальными числом состояний.

Алгоритм минимизации числа состояний автомата S = {a_p A, Z, W, 5,

состоит из следующих шагов.

1. Находятся последовательные разбиения П_р П₂, ..., П_к, П_к+1 множества A на классы одно-, двух-, ..., к, к+1-эквивалентных состояний, до тех пор пока на каком-то к+1-м шаге не окажется, что П_к+1= П_к. Нетрудно показать, что тогда разбиение Р_к = P, т. е. что k-эквивалентные состояния являются в этом случае эквивалентными и число шагов к, при котором П_к = П, не превышает М-1, где M- число элементов в множестве A.

2. В каждом классе эквивалентности разбиения П выбираются по одному элементу, которые образуют множество A’ состояний минимального автомата S’={a^, A’, Z’, W, 5’, X’}, эквивалентного автомату S.

3. Функции переходов 5’ и выходов X’ автомата определяются на множестве A’xZ. Для этого в таблице переходов и выходов вычеркиваются столбцы, соответствующие не вошедшим во множество A’ состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества A’.

4. В качестве a^ выбирается одно из состояний, эквивалентное состоянию a₁. В частности, удобно за а^ принимать само состояние а_?

В качестве примера рассмотрим минимизацию автомата Мили S, заданного таблицами переходов и выходов (табл. 9.1 и 9.2). Непосредственно по таблице выходов получим разбиение П₁ на классы одноэквивалентных состояний, объединяя в эквивалентные классы одинаковые столбцы: П₁={В₁,В₂}, B₁={a₁, a₂, a₅, a₇, a₈}, B₂={a₃, a₄, a₆, a₉, a₁₀, a_n, a₁₂}. Действительно, два состояния 1-эквивалентны, если их реакция на всевозможные входные слова длины 1 совпадают, т. е. соответствующие этим состояниям столбцы в таблице выходов должны быть одинаковы.

Таблица 9.1

аі а2 аз а4 а5 аб а7 а8 а9 аіо а11 аі2 Z алп а а а а а а а а а а а 1 10 12 5 7 3 7 3 10 7 1 5 2 Z. а а а а а а а а а а а а 2 5 8 6 11 9 11 6 4 6 8 9 8

Таблица 9.2

а1

a

a

a4

a

a6

a

a

a

aiH

a11

ai2

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

W

Строим таблицу П₁ (табл. 9.3), заменяя состояния в табл. 1 соответствующими классами 1-эквивалентности. Очевидно, что 1-эквивалент-ные состояния a , а будут 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные.

Таблица 9.3

B

B.

a

a

a

a

a8

a

a4

a6

a

ai0

au

a1

B

B

B

B

B

B

B1

B1

B1

B1

B1

Z

B

B

B

B

B

B

B

B

B

B1

B

B1

По табл. 9.3 получаем разбиение П₂ на классы 2-эквивалентных состояний (табл. 9.4): П₂={С_р C₂, C₃, C₄}, C₁={a₁, a₂}, C₂={a₅, a₇, a₈},

C3={a3, a4, a6, a9, ai1}, C4={ai0, ai2}.

Аналогично построим n₃={D_p D₂, D₃, D₄, D₅}, D₁={a₁, a₂}, D₂={a₅, a₇}, D₃={a₈}, D₄={a₃, a₄, a₆, a₉, a₁₁}, D₅={a₁₀, a₁₂} (табл. 9.5) и, наконец, П₄={Е₁, E₂, E₃, E₄, E₅}, которое совпадает с П₃. Процедура разбиения завершена. Разбиение П₃ есть разбиение множества состояний автомата Мили S на классы эквивалентных между собой состояний.

Таблица 9.4

C

C2

C3

C4

a

^2

A

a

a8

a3

a4

a6

a9

au

am

ai2

Z,

C4

C4

C3

C3

C4

C2

C2

C2

C2

C2

C

C

Z2

C2

C2

C3

C3

C3

C3

C3

C3

C3

C3

C2

C2

Таблица 9.5

D D2 D3 D4 D a a2 a5 a7 a8 a3 a4 a6 a a11 aio a12 Z D D D D4 D D2 D2 D2 D2 D2 D1 D1 Z2 D2 D2 D D4 D4 D4 D4 D4 D4 D4 D D

Выберем произвольно из каждого класса D₁, D₂, D₃, D₄, D₅ по одному состоянию. Пусть, например, A,={a₁, a₅, a₈, a₃, a₁₀}. Удаляя из первоначальных таблиц переходов (табл. 9.1) и выходов (табл. 9.2) “лишние” состояния а₂, а₇, а₄, а₆, а₉, а₁₁, а₁₂, определяем минимальный автомат Мили S₁ (таблица переходов 9.6 и таблица выходов 9.7), эквивалентный автомату S.

При минимизации автоматов Мура вводится понятие 0-эквивалентности состояний и разбиения множества состояний на 0-классы: 0-экви-валентными называются любые одинаково отмеченные состояния автоматов Мура. Если два 0-эквивалентных состояния любым входным сигналом переводятся в два 0-эквивалентных состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автоматов Мура определяются аналогично приведенному выше для автоматов Мили. В результате применения алгоритма минимизации к автомату Мура S₃ (табл.9.8), имеющему 12 состояний, получим автомат S₄ с 4 состояниями (табл. 9.9). Опуская промежуточные таблицы, приведем лишь последовательность разбиений

Bv B3}. Таблица 9.8

W1 W W3 W3 W3 W2 W3 W W W2 W2 «1 «2 «3 «4 «5 «6 «7 «8 «9 «10 «11 «12 Z «10 «12 «5 «7 «3 «7 «3 «10 «7 «1 «5 «2 Z2 «5 «7 «6 «11 «9 «11 «6 «4 «6 «8 «9 «8

B1 {ai, a2, a8}; B2 {a6, a9, ai0, ai1, ai2}; B3 {a3, a4, «5, a7}; П1={С1, C2, C3, C4}; Ci={ai, a2, a8}; C2={a6, a9, al1}; C3={ al0, al2}’ C4 {a3, «4, «5, a7}? ^, Ац D4}; A=A; Di=Ci; D2=C2; D3=C3; D4=C4.

Таблица 9.7

«1 ^5 «8 «3 «,0 Z1 W W1 W W2 W2 Z2 W2 W2 W2 W W1

Таблица 9.6

«1 «5 «8 «3 «,0 Z1 «10 «3 «10 «5 «1 Z2 «5 «3 «3 «3 «8

Таблица 9.9

W W W2 W3 a, a a,n a, z, аЛп a a a Z2 a3 a 6 a1 a 6

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

10. МЕТОДЫ КОДИРОВАНИЯ состояний АБСТРАКТНЫХ АВТОМАТОВ

Процесс кодирования состояний абстрактных автоматов является первым этапом канонического метода структурного синтеза автоматов. Кодирование заключается в установлении взаимно однозначного соответствия между множеством A = {a₁, ..., a_m} состояний автомата и множеством ^-компонентных векторов {к₁, ..., k_m}, k_m={A,_m1, ..., X_mR}, где A,_mi - состояние r-го элемента памяти (триггера). Обычно кодирование производится с помощью символов двоичного структурного алфавита (k_m^ {1,0}), поскольку при этом решается задача определения необходимого числа триггеров, имеющих два устойчивых состояния. Зависимость числа триггеров от количества состояний заданного абстрактного автомата определяется формулой [2]:

R ^ ]log₂M[,

где ]b[ означает ближайшее целое число, большее b или равное ему, если b - целое.

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

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

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

10.1. Противогоночное кодирование методом развязывания пар переходов

В литературе [4] предлагается метод противогоночного кодирования, основная идея которого сводится к следующему.

Пусть (а, в) и (у, 5) - две пары двоичных кодов произвольной длины, например

a - 1|0|1 1 у -0|1|1 1 в - 0|0|1 1 5 -0|1|0 0

Если некоторый г-й разряд кода принимает одно значение на паре (a, в) и противоположное - на паре (у, 5), то такие пары кодов называются развязанными.

Доказана следующая теорема [3]: в автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда и только тогда, когда для любых двух переходов (a_m, a_s) и (a_k, а), аФа, происходящих под действием одного и того же входного сигнала, соответствующие пары кодов развязаны. (Если автомат синхронный, то развязывать нужно пары переходов, для которых (a_m, a_s)n(a_k, а)=0). В этой же работе приведен основанный на этой теореме алгоритм про-тивогоночного кодирования состояний конечных автоматов, основная идея которого достаточно проста: последовательно просматривая все пары переходов, для которых имеется хотя бы один общий входной сигнал, осуществляющий эти переходы, следует присвоить разрядам кодов такие значения, чтобы существующие пары кодов состояний были развязаны.

Алгоритм противогоночного кодирования заключается в последовательном развязывании подлежащих развязыванию пар переходов. На промежуточных этапах алгоритма состояниям автомата будут соответствовать коды, значения некоторых разрядов которых могут быть не определены. Такие коды будем называть неполными. В дальнейшем неопределенные разряды кодов отмечаются черточкой. Пусть (a_m, a_s), (a_k, а) - пара переходов автомата S, а a, в, Y, 5 - соответственно четверка кодов (быть может, неполных) состояний а_т, а, а_к, а₁ длины i.

Операция развязывания пары переходов (a_m, a_s), (a_k, a) сводится к нескольким этапам.

1. Положить i = 0. Перейти к п.2.

2. Если i = 0, то переход к п.8, иначе переход к п.3.

3. Если при некотором r (1 < r < i) значения r-го разряда четверки а, в, у, 5 образует набор 0011 или набор 1100, то переход к п.9, иначе к п.4.

4. Если при некотором r (1 < r < i) значения r-го разряда четверки а, в, у, 5 образует один из наборов

- 0 1 1	- - 1 1	- - - 1
0 - 1 1	0 - - 1	0 - - -
1 о о	0 0 - -	- 0 - -
0 0 1 -	- 0 - 1	- - 1 -
- 0 1 -	0 - 1 -	?

то переход к п.5, иначе к п.6.

5. Доопределить неопределенные значения r-го разряда четверки а, в, Y, 5 так, чтобы его значения образовывали набор 0011. Переход к п.9.

6. Если при некотором r (1 < r < i) значения r-го разряда четверки а,

в, Y, 5 образует один из наборов

- 1 0 0 - - 0 0 ---0

1 - 0 0 1 - - 0 1---

1 1 - 0 1 1 - - - 1 - -

1 1 0 - - 1 - 0 - - 0 -

- 1 0 - 1 - 0 - ----,

то переход к п.7, иначе переход к п.8.

7. Доопределить неопределенные значения r-го разряда четверки а, в, Y, 5 так, чтобы значения этого разряда образовывали набор 1100. Переход к п.9.

8. Дополнить коды состояний автомата одним неопределенным разрядом. Увеличить r на единицу. Переход к п.4.

9. Пара переходов (a_m, a_s), (a_k, aj), развязана. Конец.

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

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

Таблица 10.1

	a	О,	a3	a4	0 5	a6	a7
Z,	c.l	a	a	a	a	a
	ai	a3	a3	ai	a3	-	-
Z3	-	a5	a7	-	a5	-	a7

Очевидно, что пары должны быть развязаны в каждом из массивов переходов M₁, M₂, M₃, происходящих под действием сигналов Z₁, Z₂, Z₃:

M1	M2	M3
(a1, a2)	(a1, a1)	(a2, a5)
(a2, a2)	(a2, a3)	(a3, a7)
(a3, a4)	(a3, a3)	(a5, a5)
(a4, a4)	(a4, a1)	(a7, a7)
(a5, a6) (a6, a6)	(a5, a3)

Развязывание пар переходов в M₁ начнем с первого перехода (a₁, a₂). Согласно сформулированной выше теореме пару (a₁, a₂) и (a₂, a₂) развязывать не надо из-за совпадения состояний перехода. Первая пара переходов, которая подлежит развязыванию, есть (a₁, a₂), (a₃, a₄). Вводим переменную t₁ и образуем по этой переменной четверку (0011) для состояний a₁, a₂, a₃, a₄. Рассматриваемая пара переходов развязана (табл.10.2).

Паре переходов (a₁, a₂), (a₄, a₄) соответствует четверка (0011) (табл.10.2), т. е. эта пара тоже развязана.

Пара (a₁, a₂),(a₅, a₆) образует четверку (00--). Для развязывания

этой пары доопределим эту четверку до (0011), для чего состояниям a₅, a₆ ставим в соответствие t₁= 1 (табл. 10.3).

Таблица 10.2 Таблица 10.3 Таблица 10.4

_Т_ T1 T1 T2 аі 0 ai 0 ai 0 - 0 Я2 0 a2 0 - аз 1 аз i a3 1 0 Я4 1 Я4 i a4 1 0 Я5 - Я5 i a5 1 1 Я6 - a6 i a6 1 1 Я7 - a - a7 - -

Из табл.10.3 видно, что пара (a₁, a₂), (a₆, a₆) развязана (четверка (0011)). Точно так же развязаны пары, образованные переходом (a₂, a₂) и всеми последующими переходами в M₁. Обратимся к паре (a₃, a₄), (a₅, a₆). Из табл. 10.3 получаем соответствующую четверку (1111) - пара не развязана. Вводим переменную t₂ и полагаем для a₃ и a₄ значение т₂=0, а для a₅ и a₆ т₂= 1 (табл. 10.4).

После чего остальные переходы в M₁ тоже развязаны. Аналогично для М₂ и М₃ получим табл.10.5 и 10.6.

Таблица 10.5 Таблица 10.6

	T1	T	T3	T1	T2	T3	T4
«1	0	1	1		1	1	1	-
	0	0	0	a2	0	0	0	0
a3	1	0	0	a3	1	0	0	1
«4	1	0	1	«4	1	0	1	-
«5	1	1	0	«5	1	1	0	0
«6	1	1	-	«6	1	1	-	-
«7	-	-	-	«7	-	0	-	1

Переходим к минимизации. Исключаем переменную Т₁ (табл. 10.7) и повторяем процесс развязывания пар переходов.

Оказывается, что пара (a₁, a₂), (a₅, a₆) не развязана, в связи с чем добавляем переменную т₅ и развязываем эту пару (табл. 10.8).

Все остальные пары развязаны. Далее исключаем переменную т₂ и получаем табл.10.9 с тремя переменными т₃,т₄, т₅, в которой после проверки оказываются развязанными все пары.

Таблица 10.7

Т2 Т4 а1 1 1 - а2 0 0 0 аз 0 0 1 а4 0 1 - а5 1 0 0 a6 1 - - а7 0 - 1

Таблица 10.8

T2 T4 ai 1 1 0 0 a2 0 0 0 0 a3 0 0 1 - a4 0 1 1 - a5 1 0 0 1 a6 1 - - 1 a7 0 - 1 - Таблица 10.10 T4 a1 1 0 0 a2 0 0 0 a3 0 1 0 a4 1 1 0 a5 0 0 1 a6 1 0 1 a7 0 1 1

Таблица 10.9

T4 а1 1 0 0 a2 0 0 0 a3 0 1 - a4 1 1 - a5 0 0 1 a6 - 0 1 a7 - 1 -

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

10.2. Противогоночное соседнее кодирование

Второй способ кодирования, позволяющий избавиться от гонок, -это кодирование соседних состояний автомата соседними кодами (соседнее кодирование). Соседние состояния - это состояния, связанные дугой на графе автомата, а соседние коды - это двоичные наборы, отличающиеся только одним разрядом. Расстояние по Хэммингу у таких кодов равно 1. При соседнем кодировании при переходе автомата из одного состояния в другое меняется состояние только у одного элемента памяти и состязания становятся невозможными. Соседнее кодирование не всегда оказывается возможным [4] и в этом случае приходится на графе между соседними состояниями автомата вставлять дополнительные, так называемые неустойчивые состояния. Неустойчивое состояние автомата (состояние а_к, на рис. 10.1) отличается тем, что под действием некоторого входного сигнала Z_k, по длительности превышающего время перехода в это состояние a_k, автомат может его “проскочить”, перейдя сразу в следующее состояние a_s.

Рис. 10.1

В процессе добавления неустойчивых состояний необходимо следить за тем, чтобы значение выходного сигнала при этом не менялось. Для того чтобы удобнее было находить коды соседних состояний, целесообразно воспользоваться диаграммой Вейча. Число клеток необходимой диаграммы определяется как 2k, где к - число соседей у того состояния автомата, которое имеет их больше всех остальных состояний. Рассмотрим пример кодирования соседними кодами состояний фрагмента графа некоторого автомата, приведенного на рис. 10.2.



Состоянием с максимальным числом соседей (к = 6) является состояние a₀. Следовательно, для кодирования удобно воспользоваться диаграммой Вейча размером 8x8=64=42 клеток (рис. 10.3). Поместим состояние a₀ в произвольную клетку диаграммы, например соответствующую коду 110110 (QQ₂ Q ₃Q₄ Q₅ Q ₆). Эта клетка имеет 6 соседних клеток, куда целесообразно помещать все состояния, соседние a₀. Тогда получим следующие коды состояний:

k(a₀) - 110110, k(a₁) - 110100, k(a₂) - 110010, k(a₃) - 100110

_Q

_ 62

Q

Ь2 Ь3 ai Ь1 a3 ao a5 a6 a7 a2 a4

Рис. 10.3

Q₆ Qs Q

Очевидно, коды состояний a₁, a₂, a₃ отличаются от кода состояния a₀ только одним разрядом. Поскольку состояние a₅ является одновременно соседним и для a₀, и для a₁, необходимо поместить его в такую клетку, которая имела бы минимальные расстояния от обоих этих состояний. Такими клетками являются клетки с кодами 010100 и 010110. Выберем одну из них (например, 010110). Тогда, чтобы обеспечить соседнее кодирование, придется ввести дополнительное неустойчивое состояние b₁, используя для него второй из этих кодов, а именно код 010100.

После этого оставшиеся состояния a₄ и a₆ можно поместить в клетки с кодами 110111 и 111110 соответственно. Состояние a₇, соседнее состояниям a₃ и a₂, удачно помещается в клетку 100010, но при этом не получается требуемых соседних кодов у состояний a₇ и a₁. Поэтому на переходе a₇ ^ a₁ необходимо ввести дополнительные состояния (меньше двух при выбранном кодировании не получается) b₂ и b₃, расположенные соответственно в соседних клетках (a₇ с b₂, b₂ с b₃, b₃ с a₁).

В результате кодирования число состояний графа увеличилось на 4 (рис. 10.4), что, естественно, уменьшает быстродействие автомата.

107

Рис. 10.4

Коды состояний, полученных в результате соседнего кодирования, приведены в табл. 10.11.

Таблица 10.11

Состояние абстрактного автомата Двоичный код Соответствующие состояния элементов памяти а0 110110 Q1 Q2 Q3 Q4 Q5 Q6 a 110100 Q Q2 Q3 Q4 Q Q6 a2 110010 Q1 Q2 Q3 Q4 Q Q6 a3 100110 Q1 Q^ Q3 Q4 Q5 Q6 a4 110111 Q1 Q2 Q3 Q4 Q5 Q6 a5 010110 Q1 Q2 Q3 Q4 Q Q6 a6 111110 Q1 Q2 Q3 Q4 Q Q6 a7 100010 Q1 Q2 Q3 Q4 Q Q6 Ь1 010100 Q1 Q2 Q3 Q4 Q Q6 b2 100000 Q1 Q2 Q3 Q4 Q Q6 b3 110000 Q1 Q2 Q3 Q4 Q Q6

Следует отметить, что в графе переходов можно найти такие пары соседних состояний (a_m h^ a_s), которые не требуют соседнего кодирования. В этом случае коды, появляющиеся в результате состязаний (ложные коды), могут быть использованы для кодирования состязаний автомата, удовлетворяющих одному из следующих условий:

1) кодируемое ложным кодом состояние (а) должно быть устойчивым по отношению к входному сигналу z_k, (рис. 10.5); поскольку под действием z_k автомат из a_t никуда перейти не может, состязания, если они и возникнут, являются некритическими;

2) из состояния а. отсутствует переход по сигналу z_k;

3) из кодируемого ложным кодом состояния a. под действием сигнала z_k автомат переходит в нужное состояние a_s (рис.10.6).

ООП 1001

Рис. 10.6

Рис. 10.5

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

10.3. Кодирование состояний автомата, близкое к соседнему

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

Рассмотрим эвристический алгоритм кодирования состояний [4] и минимизирующий суммарное число изменений элементов памяти на всех переходах автомата.

Введем весовую функцию W = Xt, где t_ms = |K_m-K_s|2 - расстояние между кодами состояний a_m и а, равное числу элементов памяти, изменяющих свое состояние на переходе (a_m, a_s); суммирование производится по всем переходам автомата. Введенная функция W может служить одной из оценок сложности комбинационной схемы автомата S, при этом упрощение комбинационной схемы будет тем больше, чем меньше W.

Алгоритм состоит из нескольких шагов.

1. Построим матрицу

аі Рі

a_r в_г

aR Pr

состоящую из всех различных пар номеров (a_r, b_r), таких, что в автомате S есть переход из a_ar в а^_г-

2. Переставим строки в матрице так, чтобы выполнялось условие

К, Р_г}п{а_р рі, ..., а_г_і, р_гЧ}*0, r=2, ..., R. (10.1)

Условие (10.1) означает, что хотя бы один из элементов r-й строки содержится в какой-нибудь из предыдущих строк. Имеются в виду только связные автоматы S, для которых такая перестановка всегда возможна.

3. Закодируем состояния из первой строки матрицы M следующим образом:

Ка1 = (00 ... 00); K_P1 = (00 ... 01).

4. Вычеркнем из матрицы M первую строчку, соответствующую закодированным состояниям а_а1, и а^₁. Получим матрицу M’.

5. В силу условия (1) в начальной строке матрицы M закодирован один элемент. Выберем из первой строчки матрицы M’ незакодированный элемент и обозначим его через у.

6. Построим матрицу М^, выбрав из M’ строчки, содержащие у. Пусть

В = {у₁, ..., Y, ..., y_F} - множество элементов из матрицы М^, которые уже закодированы. Их коды обозначим К_уР ..., ..., K_yF соответствен

но.

7. Для каждого Kf (f= 1, ..., F) найдем - множество кодов, соседних с К^ и еще не занятых для кодирования состояний автомата.

F

Построим множество = U С . Если D^ = 0 , то строим новое мно-

F f=1

жество Dy = U С2 , где С^ - множество кодов, у которых кодовое

f=1

расстояние с кодом Kf равно двум. Если Dy = 0, строим аналогично Dy,... DY, до тех пор пока не найдется D^ Ф 0 (п = 1, 2, 3, ...). Пусть

D = { K81’ ..., Kg.... ЗД.

8. Для каждого K_5g находим Wf = | K_bg - Kf |2 - кодовые расстояния между K_bg и всеми использованными кодами Kf (f = 1, ..., F). Если в автомате имеется переход из af в а_у и из а_у в af то Wf, входит дважды в W_g (см. ниже примеры переходов (a₄, a₅) и (a₅, a₄)).

9. Находим W_g = X W_f g = 1, ..., G.

10. Из DП выбираем K^ у которого W_g = min W_g. Элемент у (состояние aY) кодируем кодом K^.

11. Из матрицы M’ вычеркнем строчки, в которых оба элемента закодированы, в результате чего получим новую матрицу, которую такие обозначим через M’. Если в матрице M’ не осталось ни одной строчки, переходим к п.12, иначе к п. 5.

12. Вычисляем функцию W = Xt_ms, где t_ms = |K_m- K_s|2.

13. Конец.

Оценкой качества кодирования по рассмотренному алгоритму может служить число k = W/p, где p - число переходов в автомате. Очевидно, что к > 1, причем чем меньше значение k, тем ближе кодирование к соседнему , при котором к = 1.

Без подробных объяснений приведем пример кодирования состояний автомата, граф которого изображен на рис. 10.7.



Кодирование будем иллюстрировать диаграммой Вейча.

	00	01	11	10
0	1	2
1

_ Q

_ Q3

2 4









5 4 5 1

м' =

B4 ={2}.

Y = 4;

C₂1={101, 011}; Д} = C₂1={101, 011}. ^₁₀₁=|101-001|2=1; ^₀₁₁=|011-001|2=1. Выбираем K₄=101.

00 01 11 10 0 1 2 1 4

Qi _ Q2 _ Q3

Y =5;

C2={011}; C4={100, 111}; C}={100, 010}; d} =C и C{u C/={011, 100, 111, 010}. fF_o11=|011-001|2+|011-101|2+|011-10112+1011-000| 2= 1 +2+2+2=7; W₁₀₀=|100-001|2+|100-101|2+|100-101|2+|100-000|2=2+1+1+1=5; W_n1=|111-001|2+|111-101|2+|111-101|2+|111-000|2=2+1+1+3=6; W₀₁₀=|010-001|2+|010-101|2+|010-101|2+|010-000|2=2+3+3+1=9.

W₁₀₀=min{ W₀₀₁, W₁₀₀, W₁₁₁, W₀₁₀}. Следовательно выбираем K₅=100.

B3 ={2,4}.

Y = 3; M3

	00	01	11	10
0	1	2
1	5	4

C ={011}; C4={111}; D} = с‘иC4={011, 111}.

W₀₁₁=|011-001|2+|011-101|2=1+2=3;

W₁₁₁=|111-001|2+|111-101|2=2+1=3.

W₀₁₁=W₁₁₁. Следовательно выбираем K₃= 011.

	00	01	11	10
0	1	2	3
1	5	4

10.4. Соседнее кодирование логически смежных состояний

Существует другой метод кодирования состояний, позволяющий упростить полученную в результате структурного синтеза схему [4]. Суть этого метода заключается в использовании двух следующих правил кодирования.

Правило 1. Те состояния, из которых возможны переходы в одни и те же состояния хотя бы для одного значения входного сигнала, являются логически смежными и должны быть закодированы соседними кодами.

Правило 2. Логически смежными являются состояния, следующие для одного и того же состояния. Их необходимо кодировать соседними кодами.

Если при использовании этих правил невозможно закодировать соседними кодами все логически смежные состояния, то приоритет должен сохраниться за правилом 1.

В таблице переходов состояния, удовлетворяющие правилу 1, должны иметь одинаковые состояния перехода в какой-либо строке. Состояния, удовлетворяющие правилу 2, находятся в одном столбце таблицы переходов.

Рассмотрим таблицу переходов автомата (табл. 10.12).

Таблица 10.12

а0 ai a a3 a4 a5 a6 0 a3 a2 a a5 - ai - 1 a a a a a a a а - а1 a1 a6 a6 - ai

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

В нашем примере это:

(a₀, а₂) - оба переходят в а₃ по сигналу “0”;

(a₀, a₃) - оба переходят в a₄, по сигналу “1”;

(a₂, a₅) - оба переходят в a₅ по сигналу “1”;

(a₄, a₆) - оба переходят в a₈ по сигналу “1”;

(a₃, a₄) - оба переходят в a₆ по сигналу “а “;

(a₁, a₂, a₆) - все переходят в a₁ по сигналу “a”.

Далее необходимо выписать группы состояний, находящихся в одних и тех же столбцах. В нашем примере это (a₃, a₄), (a₂, a₁), (a₂, a₃, a₁),

(a3, a₃, aj), (a5, a4, a6), (a2, a6)? (ai, a5).

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

	K	K	K3	K4 K5
*(%. a)	*{al, a2)	*(a2- a5)	*(ay a4)	К a5) *Ц, a6)
*а a2)	*(av a6)	*(a2’ a6)	a a5)	*(a4’ a6)
	a a5)	a a3)
	a a3)

Пары состояний, полученные в соответствии с правилом 1, отмечены знаком *.

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

ai	a2	a5	a6
	a0	a3	a4

a _Q

2

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

(a₂, a₆), (a₂, a₃), (a₅, a₄), (a₁, a₅), (a₁, a₃).

В результате получили следующие коды состояний:

K(aj) = 000 (Q i Q 2 Q 3);

K(a2) = 100 (Qj Q 2Q 3);

K(a3) = 111 (Qj Q2 Q3);

K(a_A )= 011 (q 1 02 в₃);

K(a₅) = 110 (Qi Q 2 Q 3);

K(a₆) = 010 (Q 1 02 Q 3).

Процесс кодирования характеризуется качеством кодирования (k), которое рассчитывается по формуле где m - число пар логически смежных состояний, которые удалось закодировать соседними кодами; n - общее количество пар состояний, сформированных в классах K₁, K₂, ..., K_N

9

В рассматриваемом примере к = ~ 0,69.

Хорошим можно считать кодирование, у которого k>0,5.

Библиографический список

1. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988.

2. Глушков В. М. Синтез цифровых автоматов. М.: Физматгиз, 1962.

3. Мацевитый Л. В., Денисенко Е. Л. О кодировании внутренних состояний некоторых многотактных устройств// Кибернетика. 1966. №1.

4. Баранов С. И. Синтез микропрограммных автоматов. Л.: Энергия, 1979.

5. Козин И. В., Лупал А. М. Проектирование цифровых автоматов управления и контроля/ ЛИАП. Л., 1985.

6. Мелехин В. Ф, Дурандин К. П. Вычислительные машины и системы. СПб.: Высшая школа, 1993.

    Учет: Делопроизводство - Автоматизация - Софт

• Управленческий учет
  
• Технологии управленческого учета
  
  
• Делопроизводство
  
• Стандарты делопроизводства
  
• Делопроизводство предприятия
  
• Секретарь и делопроизводство
  
• Автоматизация делопроизводства
  
  
• Документооборот
  
  
• Автоматизация
  
• Автоматизация управления
  
• Практика автоматизации
  
• Софт для автоматизации