Алгебраические операции

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

3.3.1.Объединение частей автомата

Надо уметь не только разбить автомат, но и объединить полученные части. Если, например, известны части автомата A: ЦАА1, ЦАА2,...,ЦААI,...,ЦААN, то автомат А должен получится в результате объединения его частей. Такую операцию можно записать в виде:

N

ЦАА = U ЦААI.

I=1

Каждая часть характеризуется множествами входных сигналов XAI, состояний SAI и выходных сигналов YAI.

Естественно, что эти множества для результирующего автомата определятся следующим образом:

N N N

XA = U XAI, SA = U SAI, YA = U YAI .

I=1 I=1 I=1

Алгоритм объединения частей в единый автомат с использованием совмещенных матриц переходов и выходов можно представить так:

1) начать;

2) определить XA, SA и YA;

3) подготовить общую матрицу с учетом XA, SA;

4) в общую матрицу занести элементы частей;

5) закончить.

Пусть для примера требуется объединить в автомат А две его части (табл.25 и 26). Можно заметить, что эти таблицы являются копиями табл. 16 и 17. Для упрощения выполнения операции они помещены здесь, естественно номера у них заменены.

Таблица 25

1-й подавтомат

ПС ВС	s1	s2	s3
x1	s1/y2	s1/y3	s4/y4
x2	s2/y3	s4/y5	s3/ y4

Таблица 26

2-й подавтомат

ПС ВС	s4	s5	s6
x1	s6/y5	s6/y1	s5/y6
x2	s5/y6	s6/y1	s5/y1

Общая матрица (матрица результирующего автомата) имеет:

SA = SA1 U SA2,

XA = XA1 U XA2

(выходные сигналы для упрощения не рассматриваются) и представлена табл.27.

Таблица 27

СМП и В объединения частей в автомат

ПС ВС	s1	s2	s3	s4	s5	s6
x1	s1/y2	s1/y3	s2/y4	s6/y5	s6/y1	s5/y6
x2	s2/y3	s4/y5	s3/y4	s5/y6	s6/y2	s5/y1

Естественно, что должен получиться автомат, соответствующий табл. 15. Так оно и есть.

3.3.2. Настраиваемое объединение

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

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

Пусть при p=0 объединенный автомат трансформируется в ЦАА, при

р=1 - в ЦАВ, тогда

ЦАС = рЦАА U рЦАВ.

В общем виде настраиваемое объединение автоматов А и В можно написать и по другому:

ЦАС =p(ЦАА, ЦАВ).

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

ЦАА при р=0,

ЦАС =

ЦАВ при р=1.

Результирующий автомат будет характеризоваться тем, что:

XC = XA U XB,

SC = SA U SB,

YC = YA U YB.

Естественно, во множество XC будет входить переменная р.

Алгоритм настраиваемого объединения можно сформулировать так:

1) начать;

2) пометить элементы первого автомата с помощью р, а второго - с помощью р;

3) определить XС, SС и YC;

4) в общую матрицу занести элементы ЦАА и ЦАВ с учетом р;

5) упростить общую матрицу по возможности;

6) закончить.

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

Общие части автоматов после минимизации оказались без дополните-льной переменной.

Таблица 28

СМП и В ЦАА

ПС ВС	s1	s2	s3	s4
x1	s2/y2	s3/y1	s1/y3	s1/y2
x2	s3/y3	s1/y2	s2/y2	s3/y2
x3	s1/y1	s3/y3	s3/y2	s1/y3

Таблица 29

СМП и В ЦАВ

ПС ВС	s1	s2	s3	s4
x1	s4/y2	s1/y1	s4/y4	s3/y3
x2	s3/y3	s1/y2	s1/y4	s1/y4
x3	s1/y1	s3/y3	s2/y3	s2/y2

Таблица 30

Настраиваемое объединение

ПС ВС	s1	s2	s3	s4
x1	_ ps2/y2   ps4/y2	_ ps3/y1   ps1/y1	_ p s1/y3   ps4/y4	_ ps1/y2   ps3/y3
x2	s3/y3	s1/y2	_ ps2/y2   ps1/y4	_ ps3/y2   ps1/y4
x3	s1/y1	s3/y3	_ ps3/y2   ps2/y3	_ ps1/y3   ps2/y2

3.3.3. Пересечение автоматов

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

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

ЦАС= ЦАА /\ ЦАВ.

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

Для данной операции:

SC = SA /\ SB,

XC = XA /\ XB,

YС = YA /\ YB.

Становятся известными элементы матрицы С (табл. 31).

Таблица 31

Пересечение

ПС ВС	s1	s2	s3	s4
x1
x2	s3/y3	s1/y1
x3	s1/y1	s3/y3

3.3.4. Вычитание

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

Данную операцию можно записать так:

ЦАС = ЦАА \ ЦАВ (прямая разность),

ЦАD = ЦАВ \ ЦАА (обратная разность).

Для разностей имеет место:

SC < SA,

XC < XA,

YC < YX ( прямая разность),

SD < SB,

XD < XB,

YD < YB (обратная разность).

ЦА прямой разности (табл.32) будет представлять 1-й ЦА с удалением общих переходов. Естественно, что и выходной сигнал, даже если он не является общим, должен быть удалён.

ЦА обратной разности (табл.33) будет являться частью второго автомата, полученной при удалении из него общих переходов и выходных сигналов.

Таблица 32

Прямая разность

ПС ВС	s1	s2	s3	s4
x1	s2/-	s3/-	s1/y4	s2/y2
x2			s2/y1	s3/y2
x3			s3/y2	s1/y3

Таблица 33

Обратная разность

ПС ВС	s1	s2	s3	s4
x1	s4/y2	s1/y1	s4/y4	s3/y3
x2	-	-	s1/y4	s1/y4
x3	-	-	s2/y3	s2/y2

3.3.5. Симметрическая разность

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

Данную операцию можно записать так:

ЦАС=ЦАА Q ЦАВ.

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

3.3.6. Дополнение

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

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

Таким автоматом может быть настраиваемое объединение исходных автома-

тов.

3.4. Операции проверки отношения

В алгебре автоматов возможны пять отношений между двумя автоматами:

1) ЦАА < ЦАВ,

2) ЦАА > ЦАВ,

3) ЦАА = ЦАВ,

4) ЦАА /\ ЦАВ = ЦА0,

5) общее отношение.

Первое отношение означает, что ЦАA является подавтоматом ЦАВ , второе - ЦАВ является подавтоматом ЦАА , третье - автомат А равен автомату В.

Четвертое отношение - это отношение типа "Нет общего". В данном случае принято говорить, что у автоматов нет ничего общего.

Пятое отношение означает, что автоматы находятся в общем отношении, следовательно, у автоматов есть как общие, так и индивидуальные элементы.

Это означает, что:

1) ЦАА \ ЦАВ не равно ЦА0,

2) ЦАВ \ ЦАА не равно ЦА0,

3) ЦАА /\ ЦАВ не равно ЦА0.

3.4.1.Проверка отношения

Для проверки отношения нужно выполнить прямую, обратную разнос-

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

Таблица 34

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

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

3.4.2. Проверка равенства

Для проверки только равенства нет нужды запускать сложную проце-

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

3.5. Операции упрощения цифрового автомата

3.5.1. Упрощение автомата за счет упрощения алгоритма

Данный цифровой автомат можно упростить, если упростить соответствующий алгоритм.

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

Очевидно, что второй алгоритм будет проще первого алгоритма, если

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

Пусть задан алгоритм с МСА, представленной в табл. 35.

Для упрощения алгоритма применяется способ, основанный на учете

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

В МСА могут быть ситуации, когда одни и те же осведомительные

сигналы определяют заход в операторную вершину и выход из нее. Зная,

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

Пусть ГСА имеет фрагмент (рис. 23), соответствующий отмеченному выше условию. Видно, что в вершину Y_i можно зайти при ХJ =1. Известно,

что вершина Y_j не изменяет сигнал ХJ. Следовательно при выходе из вершины Y_j сигнал ХJ будет продолжать оставаться равным 1. Ясно, что перехода по выходу 0 никогда не будет, будет переход только по выходу 1. Получается, что вершина ХJ при выходе из вершины Y_j не требуется (рис. 24).

Если захода в вершину Y_t из другой вершины не будет, то не потребуется и вершина Y_t. Видно существенное упрощение алгоритма. Такое упрощение алгоритма возможно и при задании последнего в виде МСА.

Таблица 35

МСА для упрощения

МСА	Y1	Y2	Y3	Y4	Y5	Y6	YK
Y0	__ Х1Х2			__ Х1Х2 Х1 Х2	Х1Х2
Y1			X2 Х1Х2				__ Х2 Х1Х2
Y2	Х1 X2				X2 Х1Х2
Y3				__ Х1	Х1
Y4						Х1Х2Х3	Х1Х2Х3 Х1Х2 Х2 1
Y5		Х1					__ Х1
Y6

Сведения о неизменяемости осведомительных сигналов можно предста-

вить в виде таблицы. Пусть для рассматриваемого алгоритма эти данные имеются (табл.36).

Данными об неизменяемости логических условий (ЛУ) вершиной Y₀ воспользоваться нельзя, так как нет возможности установить, при каких значениях Х1, Х2 и Х3 осуществляется заход в вершину Y₀ (в МСА не бывает столбца с Y₀).

Следует начать с выяснения значений логических условий захода в вершину Y₁. Видно, что заходы осуществляются из вершин Y₀ и Y₁ при одних и тех же значениях Х1 и Х2 , а именно, при Х1=1 и Х2=0.

Знать вершины, из которых имеют место выходы, нет необходимости. Надо выяснить только, при каких одинаковых условиях есть заход. Такой заход удобно представить в виде:

® Y₁ при Х1=1 и Х2=0.

0

1 XJ = 1

Y_i

XJ = 1

1

0

Y_{s Ys}

Рис. 23 Рис. 24

Вершина Y₁ не изменяет значения Х1, что целесообразно как-то отметить, например, путем обведения квадратом Х1=1 . Выходы из вершины Y₁

можно представить в виде: Y₁ ® при Х1=1 .

Следовательно, в строке Y₁ вместо Х1 нужно подставить значение 1, а вместо Х1 значение 0. В табл.35 это можно отразить зачеркиванием Х1 и

вычеркиванием Х1Х2.

Таблица 36

Сведения о неизменяемости ЛУ

Для вершины Y₂ получается, что ®Y₂ при Х1 = 1, Y₂ ® при Х1 = 1. Строка Y₂ существенно упрощается.

Заход в вершину Y₃ одинаковым значением хотя бы одного осведомительного сигнала не характеризуется. Строку Y₃ упростить не представляется возможным.

Что касается захода в вершину Y₄, то ®Y₄ при Х1 = 0 . Функция пере-

хода a₄₆ становится равной 0. Захода в вершину Y₆ никогда не будет, соответствующий столбец следует вычеркнуть. Не будет и выхода из вершины Y₆. Следовательно, нужно вычеркнуть и соответствующую строку. Получится значительное упрощение алгоритма.

За счет анализа заходов в вершины Y₅ и Y₆ упрощений МСА не будет.

Алгоритм операции упрощения МСА при максимальном значении индекса N вершины Y можно сформулировать следующим образом (рис. 25):

1. Начать;

2. Положить I=1;

3. Для вершины Y_i выявить значения одинаковых логических условий захо-

да;

4. Уточнить неизменяемые логические условия захода, выявленные в п.3;

5. Подставить значения неизменяемых логических условий в строку Y_i;

6. Увеличить I на 1;

7. Проверить I<= N, при "да" перейти к п.3;

8. Закончить.

3.5.2. Упрощение цифрового автомата за счет тождеств

Данный цифровой автомат можно упростить, если применить тождества и законы алгебры логики. Этот прием уже применялся выше при реализации операции настраиваемого объединения (табл. 30) .

При предыдущем упрощении было получено для функции перехода a_4к

следующее выражение:

a_4к = Х2\/Х2.

По тождеству склеивания эта функция перехода a_4к = 1. Получается дополнительное сокращение МСА. Этим способом можно упростить функции

переходов a₀₄, a₁₃:

a_0к Х1Х2 \/ Х1Х2 = Х1, a₁₃ = Х2 \/ Х2 = Х2 .

В итоге упрощения МСА будет иметь меньше операторных и условных

вершин. Вместо 8 операторных вершин осталось 7 таких вершин. Что касае-

тся условных вершин, то уменьшение их числа легче определить по ГСА ис-

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

1

2

в

5

Рис.25. СА упрощения алгоритма

Дата добавления: 2015-07-26; просмотров: 183; Нарушение авторских прав

Мы поможем в написании ваших работ!