МПС
Структурная
схема конечного автомата (Тема) В структурной
теории автомат представляют в виде композиции двух частей: запоминающей части,
состоящей из элементов памяти, и комбинационной части, состоящей из логических
элементов. Комбинационная схема, строится из логических элементов, образующих
функционально полную систему, а память – на элементарных автоматах, обладающих
полной системой переходов и выходов. Каждое
состояние абстрактного автомата ai,
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. |
||