• Название:

    Мамаев В. Я«Дискретные автоматы»


  • Размер: 0.07 Мб
  • Формат: ODT
  • или
  • Сообщить о нарушении / Abuse

Установите безопасный браузер



Методические указания к выполнению контрольной работы

(раздел 4 - «Дискретные автоматы», темы 4.1 и 4.2.) и варианты заданий

1. Методические указания1.1. Понятие о дискретных автоматах

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

В кибернетику, однако, вошел и прочно в ней укрепился термин «дискретный автомат» или кратко просто «автомат» для обозначения гораздо более абстрактного понятия, а именно - модели, обладающей следующими особенностями:

а) на входы модели в каждый из дискретных моментов времени t1, t2, t3,_… поступают m входных величин {x0,x1,x2,…,xn–1}, каждая из которых может принимать конечное число фиксированных значений из входного алфавита Х;

б) на выходах модели можно наблюдать n выходных величин y1,…yn , каждая из которых может принимать конечное число фиксированных значений из выходного алфавита Y;

в) в каждый момент времени модель может находиться в одном из состояний z1,z2,…zn;

г) состояние модели в каждый момент времени определяется входной величиной x в этот момент и состоянием z в предыдущий момент времени;

д) модель осуществляет преобразование ситуации на входе x = {x1,x2,…,xm} в ситуацию на выходе 

y ={y1,y2,…,yn} зависимости от ее состояния в предыдущий момент времени.

Рис. 1. Дискретный автомат

 

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

Мы ограничимся рассмотрением лишь простейших из дискретных автоматов, входной и выходной алфавиты которых состоят всего из двух букв: 0 и 1. Это оправдывается тем что, как оказывается в теории автоматов, автоматы с такими "бедными" алфавитами способны решать такие же задачи, как и автоматы с любыми другими алфавитами.

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

1.2. Способы задания автоматов

Абстрактный автомат можно задать как совокупность шести объектов: входного алфавита {x0,x1,x2,…,xn–1}; выходного алфавита {y1,y2,y3,…,ym–1}; алфавита состояний {a0,a1,a2,…,an–1}; начального состояния а0; функции переходов δ(a,x), определяющей новое состояние автомата через предыдущее и входной сигнал; функции выходов λ(a,x), определяющей выходной сигнал в зависимости от состояния и входного сигнала.

Наибольшее распространение получили автоматы Мили и Мура [1].

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

a(t)=δ[a(t–1), x(t)],

y(t)=λ[a(t–1), x(t)],

t = 1, 2, 3,

а автомата Мура в виде

a(t)=δ[a(t–1), x(t)],

y(t)=λ[a(t)],

t = 1, 2, 3.

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

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

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

Поскольку области определения функций δ и λ совпадают, таблица переходов и таблица выходов могут быть совмещены в одну таблицу переходов-выходов (табл. 3). Здесь на пересечении i-й строки и j-го столбца (i  {0, 1, 2,…(h–1)}; j  {0, 1, 2,…(n–1)}) записывается новое состояние автомата a(t) и выходной сигнал, выработанный при переходе в это состояние.

Таблица 1 Таблица 2

a(t–1)

x0

x1

x2

a0

a3

a0

a1

a1

a2

a3

a0

a2

a1

a2

a3

a3

a0

a1

a2

a(t–1)

x0

x1

x2

a0

y0

y3

y2

a1

y1

y0

y3

a2

y2

y1

y0

a3

y3

y2

y1

Таблица 3

a(t–1)

x0

x1

x2

a0

a3/y0

a0/y3

a1/y2

a1

a2/y1

a3/y0

a0/y3

a2

a1/y2

a2/y1

a3/y0

a3

a0/y3

a1/y2

a2/y1

В табл. 4, 5 приведены функции переходов δ и выходов λ автомата Мура. Поскольку функция выходов λ для автомата Мура зависит только от одного параметра a(t), при совмещении таблиц переходов и выходов достаточно столбцу состояний автомата поставить в соответствие столбец выходных сигналов (табл. 6). Такая таблица называется отмеченной таблицей переходов автомата Мура.

Каждый столбец таблицы переходов-выходов задает автономный конечный автомат, т. е. автомат с фиксированным входным сигналом. Так, табл. 3 задает три автономных автомата Мили со входными сигналами x0, x1 и x2 соответственно для каждого. Отмеченная таблица переходов (табл. 6) задает три автономных автомата Мура с такими же входными сигналами.

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

Таблица 4 Таблица 5

a(t–1)

x0

x1

x2

a0

a3

a0

a1

a1

a2

a3

a0

a2

a1

a2

a3

a3

a0

a1

a2

a(t)

y(t)

0

y3

a1

y2

a2

y1

a3

y0

Таблица 6

y(t–1)

a(t–1)

x0

x1

x2

y3

a0

a3

a0

a1

y2

a1

a2

a3

a0

y1

a2

a1

a2

a3

y0

a3

a0

a1

a2

Для автомата Мили на стрелке, соединяющей состояния ai с aj, ставится значение входного сигнала х, под действием которого осуществляется данный переход, и выходного сигнала y, который вырабатывается при этом переходе (рис. 2).

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

В приведенных примерах функции δ и λ определены при всех значениях a(t–1) и x(t). Такие автоматы называются полностью определенными. Если функции δ и λ определены не на всех парах a(t–1) и x(t), то автомат называется частичным. На месте неопределенных переходов или выходов ставятся прочерки.

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

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

Для автомата Мили на стрелке, соединяющей состояния ai с aj, ставится значение входного сигнала х, под действием которого осуществляется данный переход, и выходного сигнала y, который вырабатывается при этом переходе (рис. 2).

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

В приведенных примерах функции δ и λ определены при всех значениях a(t–1) и x(t). Такие автоматы называются полностью определенными. Если функции δ и λ определены не на всех парах a(t–1) и x(t), то автомат называется частичным. На месте неопределенных переходов или выходов ставятся прочерки.

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

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

Для автомата Мили на стрелке, соединяющей состояния ai с aj, ставится значение входного сигнала х, под действием которого осуществляется данный переход, и выходного сигнала y, который вырабатывается при этом переходе (рис. 2).

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

В приведенных примерах функции δ и λ определены при всех значениях a(t–1) и x(t). Такие автоматы называются полностью определенными. Если функции δ и λ определены не на всех парах a(t–1) и x(t), то автомат называется частичным. На месте неопределенных переходов или выходов ставятся прочерки.

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

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

Рис. 2. Граф переходов-выходов автомата Мили.

Рис. 3. Граф переходов-выходов автомата Мура.

Обозначим A/ai — автомат A в состоянии ai. Состояние ai, автомата A1 эквивалентно состоянию aj автомата A2, если A1/ai и A2/aj под воздействием любой последовательности входных сигналов вырабатывают одинаковые выходные последовательности. Состояния ai и aj могут принадлежать одному автомату (т. е. A1=A2).

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

1.3. Минимизация абстрактного автомата

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

Обозначим A/ai - автомат А в состоянии аi Состояние ai автомата A1 эквивалентно состоянию aj автомата А2, если A1/ai и A2/aj под воздействием любой последовательности входных сигналов вырабатывают одинаковые выходные последовательности. Состояния ai и aj могут принадлежать одному автомату (т.е. A1 = А2).

Два автомата A1 и А2 эквивалентны, если каждому состоянию ai автомата A1 эквивалентно по крайней мере одно состояние автомата А2 и если при этом каждому состоянию aj автомата A1 эквивалентно по крайней мере одно состояние автомата А1. Группа эквивалентных состояний автомата может заменяться одни состоянием. Таким образом, задача минимизации числа состояний автомата сводится к отысканию автомата, эквивалентного заданному, с минимально возможным числом состояний.

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

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

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

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

Индуктивно можно распространить определение до i эквивалентных состояний i-o класса эквивалентности.

Если для каждого i класс эквивалентности i совпадает с (i+l)-ым классом, то он совпадает и со всеми последующими до конечного класса и называется бесконечным или финальным классом эквивалентности. Финальный класс эквивалентности можно получить за конечное число шагов.

Пример: задан граф полностью определенный автоматом Мили (рис. 4). Найти граф автомата с минимальным числом состояний, эквивалентного заданному.

Рис. 4. Граф исходного полностью определенного автомата Мили.

Построим таблицу переходов-выходов заданного автомата (табл. 7).

Таблица 7

a(t–1)

x0

x1

a0

a0/y0

a1/y1

a1

a0/y0

a2/y0

a2

a4/y1

a3/y0

a3

a1/y1

a2/y0

a4

a0/y0

a3/y0

Разбиение на группы одноэквивалентных состояний выглядит следующим образом: {a0}, {a1, a4}, {а2, a3}. Действительно, если автомат находится в состоянии а1 либо a4, то при подаче x0 и x1 автомат вырабатывает одинаковые выходные сигналы y0 и y1. Если автомат находится в состоянии a2 или а3, при подаче  х1 и х2 вырабатываются также одинаковые выходные сигналы у1 и у0.

Состояние а0 нельзя включить ни в одну из этих групп одноэквивалентных состояний, так как при подаче сигналов х0 и x1 — автомат в состоянииa0вырабатывает выходные сигналыy0и y1.

Найдем разбиение на группы двухэквивалентных состояний. Из состояний a1 и a4 при подаче x0 автомат переходит в одно и то же состояние a0, а при подачех1— в состояния a2 и а3, которые принадлежат одной группе I класса эквивалентности. Из состояний a2 и a3 при подаче х0 автомат переходит в состояние a4 и a1, а при подаче х0— в состояния а3 и a2, но пары {а4,а1} и {a3,а2} являются одноэквивалентными, следовательно, II класс эквивалентности совпадает с I классом эквивалентности, а следовательно, последний является финальным классом.

Обозначим каждую группу финального класса через новое состояние

{a0}—b0, {a1,a4}—b1, {a2,a3}—b2.

Таблица переходов эквивалентного минимального автомата представлена табл. 8, а граф минимального автомата изображен на рис. 5.

Таблица 8

b(t–1)

x0

x1

b0

b0/y0

b1/y1

b1

b0/y0

b2/y0

b2

b1/y1

b2/y0

Группы эквивлентности можно получить с помощью треугольной таблицы, которая строится следующим образом: строки обозначаются состояниями a1, a2, а3, ..., аh–1, а столбцыa0, a1, a2, ..., аh–2, где h — число состояний абстрактного автомата.

Рис. 5. Граф эквивалентного минимального автомата Мили.

На пересечении i-й строки и j-го столбца записываются условия, при которых возможно объединение состояний ai и аj. Если состояния нельзя объединить ни при каких условиях, ставится знак , если объединяются безусловно, то знак . Клетки, соответствующие пересечениям строк и столбцов с одинаковыми индексами, не заполняются. Окончательное объединение состояний определяется на основании анализа непротиворечивости условий. Для рассматриваемого примера треугольная таблица выглядит следующим образом:

Таблица 9

a1

a2

a3

a1,a4

a2,a3

a4

a2,a3

a0

a1

a2

a3

Как видно из табл. 9, состоянияa1иа4можно объединить при условии объединения состояний а2, и а3 в одну группу, а состояния a2 и а3 объединяются при условии объединения состояний а1 и a4 в одну группу, а также при объединении а2 и а3. Эти условия не являются противоречивыми, поэтому объединяются пары a1 и a4, а также а2 и а3.

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

Пример. Задан автомат Мура отмеченной таблицей переходов (табл. 10).

Таблица 10

y(t-1)

a(t-1)

x0

x1

y1

a0

a2

a4

y0

a1

a1

a2

y1

a2

a0

a2

y0

a3

a3

a1

y1

a4

a4

a0

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

{а0, а2, а4} и {а4,а3} — 0 класс,

{ao, а2, а4}, {a1} и {а3} —I класс,

{а0,a2, а4}, {a1} и {а3} —II класс, а следовательно, и финальный класс эквивалентности. Обозначив каждую группу финального класса эквивалентности новым состоянием, соответственно b0, b1 и b2, построим отмеченную таблицу переходов эквивалентного минимального автомата Мура (табл. 11).

Таблица 11

y(t-1)

b(t-1)

x0

x1

y1

b0

b0

b0

y0

b1

b1

b2

y0

b2

b2

b1

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

Таблица 12

a1

a2

a0,a2

a2,a4

a3

a1,a3

a2,a2

a4

a2,a4

a0,a4

a0,a4

a0,a2

a0

a1

a2

a3

Литература

  • Ерош И.Л., Михайлов В.В. Проектирование цифровых автоматов: учеб. пособие / И. Л. Ерош, В. В. Михайлов. СПб.: ГУАП, 2009. 92 с.:

  • Варианты заданий
  • Вариант 1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a3/w1

    a2/w1

    a1/w2

    a5/w1

    a1/w1

    a3/w2

    a7/w2

    a0/w1

    z2

    a2/w2

    a4/w2

    a6/w1

    a0/w2

    a5/w2

    a6/w1

    a4/w1

    a2/w2

    Вариант 2

    w1

    w1

    w1

    w2

    w1

    w2

    w2

    w2

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a2

    a5

    a2

    a2

    a4

    a4

    a5

    a2

    z2

    a3

    a1

    a7

    a3

    a5

    a5

    a1

    a7

    z3

    a1

    a6

    a1

    a1

    a1

    a1

    a6

    a1

    Вариант 3

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    a8

    z1

    a2/w2

    a3/w1

    a0/w2

    a6/w1

    a8/w2

    a2/w2

    a3/w1

    a3/w2

    a4/w2

    z2

    a5/w1

    a7/w2

    a3/w1

    a8/w2

    a0/w1

    a4/w1

    a2/w2

    a1/w1

    a6/w1

    Вариант 4

    w1

    w2

    w3

    w1

    w2

    w2

    w3

    w1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a4

    a3

    a5

    a2

    a3

    a1

    a5

    a4

    z2

    a6

    a7

    a3

    a1

    a0

    a2

    a3

    a2

    Вариант 5

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a6/w1

    a3/w2

    a3/w1

    a2/w1

    a1/w1

    a2/w1

    a5/w2

    a5/w1

    z2

    a5/w1

    a7/w1

    a7/w1

    a1/w2

    a3/w1

    a6/w2

    a2/w1

    a2/w1

    Вариант 6

    w1

    w2

    w3

    w1

    w2

    w2

    w3

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    z1

    a4

    a3

    a4

    a2

    a3

    a1

    a4

    z2

    a6

    a0

    a3

    a1

    a0

    a2

    a3

    Вариант 7

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a4/w1

    a3/w1

    a2/w2

    a6/w1

    a2/w1

    a4/w2

    a8/w2

    a1/w1

    z2

    a3/w2

    a5/w2

    a0/w1

    a1/w2

    a6/w2

    a0/w1

    a5/w1

    a3/w2

    Вариант 8

    w1

    w1

    w2

    w2

    w1

    w2

    w1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    z1

    a1

    a0

    a2

    a3

    a6

    a0

    a4

    z2

    a3

    a2

    a3

    a0

    a2

    a1

    a3

    z3

    a5

    a4

    a1

    a6

    a1

    a5

    a5

    Вариант 9

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    a8

    z1

    a3/w2

    a4/w1

    a1/w2

    a7/w1

    a0/w2

    a3/w2

    a4/w1

    a4/w2

    a5/w2

    z2

    a6/w1

    a8/w2

    a4/w1

    a0/w2

    a1/w1

    a5/w1

    a3/w2

    a2/w1

    a7/w1

    Вариант 10

    w1

    w1

    w1

    w2

    w1

    w2

    w2

    w2

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a3

    a6

    a3

    a3

    a5

    a5

    a6

    a3

    z2

    a4

    a2

    a0

    a4

    a6

    a6

    a2

    a0

    z3

    a2

    a7

    a2

    a2

    a2

    a2

    a7

    a2

    Вариант 11

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a7/w1

    a4/w2

    a4/w1

    a3/w1

    a2/w1

    a3/w1

    a6/w2

    a6/w1

    z2

    a6/w1

    a0/w1

    a0/w1

    a2/w2

    a4/w1

    a7/w2

    a3/w1

    a3/w1

    Вариант 12

    w1

    w2

    w3

    w1

    w2

    w2

    w3

    w1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a5

    a4

    a6

    a3

    a4

    a2

    a6

    a5

    z2

    a7

    a0

    a4

    a2

    a1

    a3

    a4

    a3

    Вариант 13

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a5/w1

    a4/w1

    a3/w2

    a7/w1

    a3/w1

    a5/w2

    a1/w2

    a2/w1

    z2

    a4/w2

    a6/w2

    a0/w1

    a2/w2

    a7/w2

    a0/w1

    a6/w1

    a4/w2

    Вариант 14

    w1

    w2

    w3

    w1

    w2

    w2

    w3

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    z1

    a5

    a4

    a5

    a3

    a4

    a2

    a5

    z2

    a0

    a1

    a4

    a2

    a1

    a3

    a4

    Вариант 15

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    a8

    z1

    a4/w2

    a5/w1

    a2/w2

    a8/w1

    a1/w2

    a4/w2

    a5/w1

    a5/w2

    a6/w2

    z2

    a7/w1

    a0/w2

    a5/w1

    a1/w2

    a2/w1

    a6/w1

    a4/w2

    a3/w1

    a8/w1

    Вариант 16

    w1

    w1

    w2

    w2

    w1

    w2

    w1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    z1

    a2

    a1

    a3

    a4

    a0

    a1

    a5

    z2

    a4

    a3

    a4

    a1

    a3

    a2

    a4

    z3

    a6

    a5

    a2

    a0

    a2

    a6

    a6

    Вариант 17

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a0/w1

    a5/w2

    a5/w1

    a4/w1

    a3/w1

    a4/w1

    a7/w2

    a7/w1

    z2

    a7/w1

    a1/w1

    a1/w1

    a3/w2

    a5/w1

    a0/w2

    a4/w1

    a4/w1

    Вариант 18

    w1

    w1

    w1

    w2

    w1

    w2

    w2

    w2

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a4

    a7

    a4

    a4

    a6

    a6

    a7

    a4

    z2

    a5

    a3

    a1

    a5

    a7

    a7

    a3

    a1

    z3

    a3

    a0

    a3

    a3

    a3

    a3

    a0

    a3

    Вариант 19

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a6/w2

    a5/w2

    a4/w1

    a0/w2

    a4/w2

    a6/w1

    a2/w1

    a3/w2

    z2

    a5/w1

    a7/w1

    a1/w2

    a3/w1

    a0/w1

    a1/w2

    a7/w2

    a5/w1

    Вариант 20

    w1

    w2

    w3

    w1

    w2

    w2

    w3

    w1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a6

    a5

    a7

    a4

    a5

    a3

    a7

    a6

    z2

    a0

    a1

    a5

    a3

    a2

    a4

    a5

    a4

    Вариант 21

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    a8

    z1

    a6/w2

    a7/w1

    a4/w2

    a0/w1

    a3/w2

    a6/w2

    a7/w1

    a7/w2

    a8/w2

    z2

    a9/w1

    a2/w2

    a7/w1

    a3/w2

    a4/w1

    a8/w1

    a6/w2

    a5/w1

    a0/w1

    Вариант 22

    w1

    w2

    w3

    w1

    w2

    w2

    w3

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    z1

    a6

    a5

    a6

    a4

    a5

    a3

    a6

    z2

    a1

    a2

    a5

    a3

    a2

    a4

    a5

    Вариант 23

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a7/w1

    a6/w1

    a5/w2

    a0/w1

    a5/w1

    a7/w2

    a3/w2

    a4/w1

    z2

    a6/w2

    a8/w2

    a2/w1

    a4/w2

    a0/w2

    a2/w1

    a8/w1

    a6/w2

    Вариант 24

    w1

    w1

    w2

    w2

    w1

    w2

    w1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    z1

    a3

    a2

    a4

    a5

    a1

    a2

    a6

    z2

    a5

    a4

    a5

    a2

    a4

    a3

    a5

    z3

    a7

    a6

    a3

    a1

    a3

    a7

    a7

    Вариант 25

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    a8

    z1

    a5/w1

    a6/w2

    a3/w1

    a0/w2

    a2/w1

    a5/w1

    a6/w2

    a6/w1

    a7/w1

    z2

    a8/w2

    a1/w1

    a6/w2

    a2/w1

    a3/w2

    a7/w2

    a5/w1

    a4/w2

    a0/w2

    Вариант 26

    w1

    w1

    w1

    w2

    w1

    w2

    w2

    w2

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a5

    a0

    a5

    a5

    a7

    a7

    a0

    a5

    z2

    a6

    a4

    a2

    a6

    a0

    a0

    a4

    a2

    z3

    a4

    a1

    a4

    a4

    a4

    a4

    a1

    a4

    Вариант 27

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a1/w2

    a6/w1

    a6/w2

    a5/w2

    a4/w2

    a5/w2

    a0/w1

    a0/w2

    z2

    a0/w2

    a2/w2

    a2/w2

    a4/w1

    a6/w2

    a1/w1

    a5/w2

    a5/w2

    Вариант 28

    w1

    w2

    w3

    w1

    w2

    w2

    w3

    w1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a7

    a6

    a0

    a5

    a6

    a4

    a0

    a7

    z2

    a1

    a2

    a6

    a4

    a3

    a5

    a6

    a5

    Вариант 29

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    z1

    a5/w1

    a7/w1

    a1/w2

    a3/w1

    a0/w1

    a1/w2

    a7/w2

    a5/w1

    z2

    a6/w2

    a5/w2

    a4/w1

    a0/w2

    a4/w2

    a6/w1

    a2/w1

    a3/w2

    Вариант 30

    w1

    w1

    w2

    w2

    w1

    w2

    w1

    a0

    a1

    a2

    a3

    a4

    a5

    a6

    z1

    a4

    a3

    a5

    a6

    a2

    a3

    a0

    z2

    a6

    a5

    a6

    a3

    a5

    a4

    a6

    z3

    a8

    a0

    a4

    a2

    a4

    a8

    a8