Алгебры автоматов

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

Все операции можно разделить на следующие пять групп:

1) группу операций декомпозиции;

2) группу операций композиции;

3) группу алгебраических операций;

4) группу операций проверки отношения между автоматами;

5) группу операций упрощения автомата.

В первую группу входят операции формирования булеана (множества

всех подавтоматов) автомата, разбиения и покрытия автомата, проверки раз-

биения и покрытия.

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

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

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

Упрощать автоматы можно на основе тождеств алгебры автоматов, на основе учета сохраняемости логических условий [4].

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

Имеющуюся форму распределительного закона в обычной алгебре следует называть формой распределения “произведения” относительно “слагаемого”.

Все тождества алгебры алгоритмов [14] действуют в алгебре автоматов. В системе тождеств выделяются группы:

1) тождеств отдельных операций;

2) тождеств склеивания;

3) тождеств поглощения;

4) тождеств Порецкого;

5) тождеств де Моргана;

6) тождеств для общих “множителя” и “слагаемого” совершенного ранга.

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

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