X,

z

X,

хг

tl Э1

Иг Yt Yz г

a{6~

7 5

a) В

1

x,

xz

Yi

г

xz

Ъ У/ z

г)

Рис. 4.3

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

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

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

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

автомата основан на выявлении эквивалентных и и объединении совместных внутренних состояний состояниями асинхронного автомата

автомата.

Метод сжатия таблицы переходов асинхронного псевдоэквивалентных состояний, а также выявлении автомата (строк таблицы переходов) [1,3]. Эквивалентными называются такие два устойчивые состояния, которые удовлетворяют следующим условиям:

1)им соответствует одно и то же состояние входа автомата (т. е. они находятся в одном и том же столбце таблицы);

2)им соответствует одно и то же состояние выхода автомата;

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

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

(1),0 7

1 1

Пусть, например, задана первоначальная таблица переходов (см. табл. 4.1). В соответствии с первым условием эквивалентными состояниями могут быть только те устойчивые состояния, которые находятся в одном столбце таблицы переходов, т. с. в нашем случае это состояния (4) и (7); (2) и (5); (3) и (6); (3) и (8); (6) и (8). Теперь из этих пар надо выбрать состояния, удовлетво ряющие второму условию, т. е. такие, которым соответствует одно и то же состояние выхода. Так как устойчивому состоянию (6) соответствует состояние выхода, противоречивое состояниям выхода, соответствующим устойчивым состояниям (3) и (8), то устойчивые состояния (3) и (6); (6) и (8) не могут быть эквивалентными. Из оставшихся пар устойчивых состояний (4) и (7); (2) к (5); (3) и (8) эквивалентными будут такие состояния, которые удовлетворяют еще и третьему условию эквивалентности.

Для того чтобы два устойчивых состояния удовлетворяли третьему условию эквивалентности, в одном и том же столбце соответствующих им строк должны стоять или одни и те же цифры, или различные цифры, но определяющие эквивалентные состояния. В нашем случае эквивалентными будут устойчивые состояния (3) и (8); (2) и (5); (4) и (7).

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

приписывание каждой группе эквивалентных состояний одного номера, например наименьшего номера состояния, входящего в эту группу;

замена всех строк, в которые входят эквивалентные состояния одной группы, одной строкой. Для рассматриваемого примера (см. табл. 4.1) устойчивое состояние (8) заменяем на (3). Аналогично состояния (7) и (5) заменяем соответственно на эквивалентные им состояния (4) и (2). Заменяем также и неустойчивые состояния 8, 7 и 5 соответственно на 3, 4 и 2. После этого получаем таблицу, в которой строки, соответствующие внутренним состояниям яз и v.&, л4 и И7; у.-г и э<5, являются попарно одинаковыми. Строки таблицы переходов, которым соответствуют эквивалентные устойчивые состояния, объединяем и получаем таблицу переходов с пятью строками (табл. 4.2).

Выше были произведены выявление и объединение эквивалентных состояний для полного автомата. Для недоопределенного автомата кроме понятия «эквивалентности» состояний введено понятие «пссвдоэквивалентности» состояний [1, З]. Псевдоэквивалентными называются такие два устойчивые состояния асинхронного автомата, которые удовлетворяют следующим условиям:

1)им соответствует одно и то же состояние входа автомата;

2)им соответствуют непротиворечивые состояния выходов автомата;

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

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

Совместимыми внутренними состояниями автомата называются состояния, при объединении которых будет получен автомат, эквивалентный исходному. Под совместимыми внутренними состояниями можно понимать таких два внутренних состояния, которым соответствуют строки с непротиворечивым размещением цифр в них, т. е. такие строки, в одном и том же столбце которых должны быть одинаковые цифры или в одной строке - цифра, а в другой - прочерк. Например, для табл. 4.2 внутренние состояния Х1 и Х5; к-2, хз и Х4 являются совместимыми.

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

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