Другие виды автоматов

Частичные автоматы. В инженерной практике нередко встречаются автоматы, на входы которых некоторые последовательности сигналов ни разу не подаются. Эти последовательности станем именовать запрещенными входными словами данного автомата, а сам автомат — частичным автоматом. У частичного автомата функции переходов и выходов определены не на всех парах а_i, х_j. На месте неопределенных состояний и выходных сигналов ставится прочерк. При синтезе традиционно производят до определение частичного автомата, чтоб его схемная осуществление вышла как можно легче. Пример переходов и выходов частичного автомата представлен в таблице 12.

Таблица 12.

Таблица переходов и выходов частичного автомата Мили.

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

• 1) Элементарные автоматы считаются автоматами Мура с 2-мя внутренними состояниями;
• 2) Автомат выдает 2 различных выходных сигнала, соответственных двум его внутренним состояниям. В предстоящем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1;

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

В качестве элементарных автоматов в вычислительной технике используются, в основном, триггеры разных типов (рисунок 5). Здесь рассмотрены некоторые из них.

Рисунок 5. Элементарный автомат.

Т-триггером называют автомат Мура с двумя устойчивыми состояниями и одним входом Т, который изменяет свое состояние на противоположное всякий раз, когда на вход Т поступает входной единичный сигнал (таблица 13).

Таблица 13. Таблица переходов Ттриггера.

Кроме того, любое состояние автомата отмечено отличным от остальных выходным сигналом. На практике наиболее комфортно за место указанных таблиц переходов воспользоваться так именуемыми матрицами переходов элементарных автоматов (таблица 14).

Таблица 14. Матрица переходов.

Матрица переходов описывает значения сигналов на входах элементарного автомата, обеспечивающие любой их 4 вероятных переходов. Здесь Q (t) и Q (t+1) — состояния автомата в моменты времени t и t+1 соответственно. Так как Т-триггер владеет один вход, а количество вероятных переходов одинаково четырем, то матрица переходов имеет 4 строки.

D-триггером (триггером задержки) именуют элементарный автомат Мура с 2-мя устойчивыми состояниями и одним входом D таким, что Q (t+1)=D (t). Название D-триггера проистекает от английского слова «dеlаy» — задержка.

Матрица переходов для D-триггера представлена в таблице 15.

Таблица 15. Матрица переходов D-триггера.

Обозначения асинхронного и синхронного D-триггеров представлено на рисунке 6:

Рисунок 6. Асинхронный и синхронный D-триггеры Схема перехода состояний D-триггера представлена на рисунке 7.

Рисунок 7. Граф D-триггера.

RS-триггером именуют автомат Мура с 2-мяустойчивыми состояниями, имеющий 2 входа R и S такие, что при S=1 и R=0 триггер воспринимает состояния 1, а при R=1 и S=0 состояние 0. В соответствие с состоянием, принимаемым триггером, вход S называет единичным входом, а вход R нулевым (таблица 16).

Таблица 16. Матрица переходов RS-триггера.

Комбинация сигналов R=1 и S=1 считается запрещенной и поэтому переход в триггере при таких значениях входных сигналов не определен. Переход триггера из 0 в 0 вероятен при 2-ух комбинациях входных сигналов: R=0, S=0 и R=1, S=0. Поэтому в первой строке матрицы переходов RS триггера в столбце R поставлена переменная b1, которая имеет возможность воспринимать 2 значения 0 v 1.

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

JK-триггером именуют автомат Мура с 2-мя устойчивыми состояниями и 2-мя входами J и K, который при условии J*K=1 исполняет инверсию предыдущего состояния (т.е. при J*K=1, Q (t+1)= Q (t)), а в других вариантах работают в соответствии с таблицей истинности RS триггера, при этом вход J эквивалентен входу S, а вход K — входу R. Данный триггер уже не имеет запрещенной комбинации входных сигналов и его таблица истинности, то имеется зависимость Q (t+1)=f[J, K, Q (t)] имеет вид (таблица 17).

Таблица 17. Таблица истинности JK-триггера.

По таблице истинности JK-триггера можно построить матрицу переходов (таблица 18).

Таблица 18. Матрица переходов JK-триггера.

В интегральной схемотехнике используются лишь синхронные JK триггера, которые при С=0 сохраняют свое состояние, а при С=1 действуют как асинхронные JK триггера.

Универсальный триггер. Триггер JK относится к уровню универсальных триггеров, так как на его основе путем легкой внешней коммутации разрешено построить RS-, Dи Tтриггера. RS-триггер получается из триггера JK простым наложением ограничения на комбинацию входных сигналов J=K=1, так как данная комбинация считается запрещенной для RS триггера.

Вероятностные автоматы с e-переходами. В теории нередко рассматривается автоматы, именуемые автоматами с e-пере-ходами (с эпсилон — переходами). Эпсилон-переходом именуется переход между состояниями, который может существовать выполнен в отсутствии входного сигнала. Эти переходы классифицируются символом e. Внедрение эпсилон-переходов позволяет просто объединять некоторое количество автоматов в один.

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

I строка состоит из одной или более цифр (0 — 9) и может заканчиваться символом «D» (например «1367» или «2345D»);

строка состоит из одного или более символов «0» или «1» и заканчивается символом «B» (например «01011B»);

строка состоит из одной или более десятичной цифр или символов от «А «до «F» и заканчивается символом «H» (например «9AD4H»).

Граф такого автомата представлен на рисунке 8.

В теории автоматов доказывается, что хоть какой вероятностный автомат имеет возможность быть заменен эквивалентным детерминированным (обычным) автоматом.

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

Рисунок 8. Граф эквивалентного детерминированного автомата имеет меньше состояний, но более сложную систему переходов.