Если в (3.25) подставить ЛСА (3.9) и (3.10), то получим ЛСА с 22 членами, включая Ay и не считая тождественно ложных логических условий <в,в которой каждый из операторов встречается дважды. Объединим ЛСА (3.9) я (3.10) так, чтобы в объединенной логической системе алгоритма каждый из операторов был бы выполнен только 1 раз.

Процесс построения объединенной ЛСА, в которой операторы не повторяются, состоит в следующем.

По матричным схемам алгоритма двух частных логических схем алгоритма составляется МСА объединенной ЛСА, каждый элемент которой

"» -X"W

где - определяющая функция, равная функции от логических условий pi=/(/-i,... ,rm), принимающей единичное значение на наборе значений переменных г\,...,Гт, который сопоставлен с ЛСА St. Если оператор А, не входит в ЛСА 21,, то в функцию рЛ соответствующий набор значений г\,..., Гт войдет в качестве условного.

В нашем случае для всех операторов логической схемы алгоритма Яисх Уг=г, а для всех операторов ЛвЛ\=г, так как в 2I1 и 21„ входят все операторы.

Таким образом, получаем следующую объединенную матричную схему алгоритма:

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

Теперь нетрудно построить объединенную ЛСА

и = vn7 Fj Pl t3 /• f5 p3t7j2 F, Pi\* rf7 ftf2 ft пв а Л2 o)}h8 4* «tn6 ft

в которой вместе с оператором Л о имеется 18 членов без учета тождественно-ложных ЛУ. Контрольные вопросы

1.Какими параметрами характеризуется конечный автомат?

2.Назовите разновидности конечных автоматов.

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

4.Укажите достоинства и недостатки языка таблиц переходов по сравнению с языком таблиц включении.

5.Почему микропрограммный автомат удобнее задавать на языке ЛСА?

Глава 4.

МЕТОДЫ АБСТРАКТНОГО СИНТЕЗА АВТОМАТОВ

4.1. Минимизация числа внутренних состояний автомата

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

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

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

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

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

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

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

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

заведомо реализующий автомат с каким-то числом внутренних состояний, которое затем сокращается (минимизируется) до такого Smin, что при Smin-1 автомат становится нереализующим.

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

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

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

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

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

Пример 4.1. Пусть задана первоначальная таблица включений, полученная е .примере 3..1 (см. рис. 3.8,г). Необходимо по .ней построить таблицу включений реализуемого авгомата.

Решение. Как видно из рис. 3.8,г, в тактах 2 и 4 имеется одно и то же состояние входа (входной сигнал JC1=l, входной сигнал -<2=" т. е. отсутств> ет4, а состояния выхода различны: в такте 2 выходной сигнал г-и, а в такте* »1. Следовательно, необходимо вводить внутренние состояния автомата, т е. элементы памяти Э,П, сигналы на входе которых (т. е. ма выходе логического преобразователя ЛП) обозначим через У), .... Y„ а на выходе (л е. входе ЛП) -через (/,, .... у.. При переводе нереализуемой первоначальной таблиды включений в реализуемую вначале делается попытка построить ее с использованием одного элемента памяти. В данном случае этот ЭП можно включить между совпадающими тактами 2 и 4, в которых при одном и том же состоянии входа имеются различные состояния выхода), т. е. только в такте и. "ыклю чить же его можно в такте 4 (рис. 4..1,а). Поскольку SH1 имеет задержку т (см. рис. 3.2), сигнал на его выходе, а значит на входе ЛП (см. рис. J.I), появится через время т, а исчезнет после снятия сигнала на входе aiii tr. е. на выходе ЛП) также через время т.

12 3567

г

J.1

у,

г

5(1)

та 5

Рис. 4.1

.Каждый из тактов 3 я 5 (1) первоначальной таблицы включении делятся на две части (рис. 4.1,6). Состояния ЭП, при которых с его выхода снимается сигнал у=1, в таблице включений показаны знаком «+». Кроме того, для наглядности такт, в котором на вход ЭП подан сигнал Уг=1, а на его выходе еще нет сигнала уг=0 (т. е. неустойчивое состояние ЭП), в строке У{ таблицы отмечается стрелкой. Такт, при котором Уг=0, а у,=1, часто вместо знака «+» отмечается знаком « ч »•

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

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

Решение. Введем вначале один ЭП, и попытаемся включить его в такте 9, который находится между совпадающими тактами 8 и 10 (рис. 4.2,я). Из рис. 4.2,а видно, что этого сделать нельзя, так как сразу же возникают новые совпадающие такты (такт 9а является совпадающим с тактами 1, rf, о и 7). Попытка включить ЭП[ в предыдущих тактах вплоть до такта 3 также при. •зодит к возникновению новых совпадающих тактов. Оказывается, что ЭП можно включить только в такте 2 (рис. 4.2,6). Однако в данном случае такты 8 я 10 по-прежнему являются совпадающими. Кроме того, появляются новые .совпадающие такты 1а и 9. Это означает, что одного элемента памяти недостаточно. Попытаемся ввести еще один элемент памяти - ЭПз. Рассуждая анаявгичным образом, получаем вновь неудовлетворительное решение-по-прежнему имеются совпадающие такты (рас. 4J2,e). Теперь, прежде чем ввести третий ЭП, попытаемся эффективно использовать четвертую комбинацию двух ЭП-;/1=0, й=1 (рис.

4.2,е).

Последовательно вводя новые ЭП и используя при этом все 2" возможные комбинации состояний включенных элементов памятя п, можно добиться перевода нереализуемых условий в реализуемые. В нашем случае таблица включении становится реализуемой при четырех ЭП (рис. 4.2,<Э).

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

Решение. Из анализа таблиц включений находим, что такт 4 первой таблицы включений (см. рис. 3.8,г) совпадает с тактом 2 этой же таблицы к с тактом 4 второй таблицы включений (см. рис. 3.9,г). Поэтому вначале включаем dlli в первой таблице. Однако, поскольку во второй таблице в такте 3 имеется то же состояние входа, что в такте 3 первой таблицы, этот элемент должен быть включен и во второй таблице (рис. 4.3,<г и б). При этом на рис. 4.3,6 такты во второй таблице перенумерованы, так как они принадлежат второй последовательности, задающей тот же автомат. Введением одного ЭП не удается перевести условия работы в реализуемые - остаются совпадающие такты 4 и 7. Поэтому необходимо ввести еще один ЭП. Он должен быть включен во вторую таблицу так, как показано на рис. 4.d,e.