В начало

Структурная схема конечного автомата (Тема)

 

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

Каждое состояние абстрактного автомата a_i, i=0,n, кодируется в структурных автоматах набором состояний элементов памяти Q2, R=1,R. Поскольку в качестве элементов памяти используются обычные двоичные триггера, то каждое состояние можно закодировать двоичным числом ai=Q1Q2….Qr. Здесь Q – состояние автомата, а ai = {0, 1}/ Как и прежде Q

 

Общее число необходимых элементов памяти можно определить из следующего неравенства 2R > n + 1. Здесь (n+1) – число состояний. Логарифмируя неравенство получим R > ]log2 (n+1)[. Здесь ]с[ - означает, что необходимо взять ближайшее целое число, большее или равное C.

 

 

 

 

 

 

 

 

 

 

В отличии от абстрактного автомата, имеющего один входной и один выходной канала, на которые поступают сигналы во входном X={x1, x2,…..,xm} и выходном Y={y1,y2,….,yk} алфавитах, структурный автомат имеет L входных и N выходных каналов. Каждый входной xj и выходной yj сигналы абстрактного автомата могут быть закодированы двоичным набором состояний входных и выходных каналов структурного автомата.

Очевидно число каналов L и N можно определить по формулам

L ³ ]log m[;

N ³ ]log k[,

аналогичным формуле для определения a3 под действием сигнала xj с выдачей сигнала yg соответствует переход структурного автомата из состояния ai в состояние as под действием сигнала xj с выдачей сигнала yg соответствует переход структурного автомата из состояния () в состояние (), под действием входного сигнала ()  с выдачей выходного сигнала (). Для того, чтобы структурный автомата перешел из одного состояния в другое, необходимо изменить состояние элементов памяти Qr.

Изменение же состояния элементов памяти происходит под действием сигналов U=(U1,U2,…,Ur) поступающих на их входы. Эти сигналы формируются комбинационной схемой II и называются функций возбуждения элементов памяти (элементарных автоматов). На вход комбинационной схемы II, кроме входного сигнала xj, по цепи обратной связи поступают сигналы Q=(Q1, Q2, …, QR), называемые функцией обратной связи от памяти автомата к комбинационной схеме. Комбинационная схема I служит для формирования выходного сигнала yg, причем в случае автомата Мили на вход этой схемы поступает входной сигнал xj, а в случае автомата Мура – сигнал xj не поступает, т.к. yg не зависит от xj.