-Поиск по дневнику

Поиск сообщений в zhurnalist

 -Подписка по e-mail

 

 -Статистика

Статистика LiveInternet.ru: показано количество хитов и посетителей
Создан: 26.11.2010
Записей:
Комментариев:
Написано: 18

Представление автомата

Дневник

Среда, 22 Декабря 2010 г. 20:56 + в цитатник
Конечный автомат удобно представлять таблицей переходов и таблицей выходов. Строкам этих таблиц соответствуют состояния автомата, столбцам – входные символы. На пересечении строки, соответствующей состоянию q, и столбца, соответствующего входному символу а, в таблице переходов записывается значение (a, q), а в таблице выходов – значение (a, q). Другими словами, в первом случае в клетке таблицы указывается состояние, в которое автомат переходит из состояния q при поступлении на его вход символа а, а во втором случае – выходной символ, который при этом выдает автомат. Табл.18.2 и табл.18.3 представляют собой пример описанного представления автомата Мили, у которого А = {a1, a2, a3, a4}, В = {b1, b2} и Q {q1, q2, q3}.
Таблица 18.2 Таблица 18.3
Функция Функция
a1 a2 a3 a4 a1 a2 a3 a4
q1 q1 q2 q1 q2 q1 b1 b1 b2 b1
q2 q3 q1 q3 q1 q2 b1 b2 b2 b1
q3 q3 q1 q1 q1 q3 b2 b2 b1 b1

Зная начальное состояние автомата и входную последовательность, нетрудно получить по этим таблицам соответствующую последовательность выходных символов. Приведем пример такого соответствия для автомата, заданного табл. 18.2 и 18.3, на вход которого поступила последовательность символов а1, а2, а2, а1, а3, а4, а1, а4 при начальном состоянии q1. Покажем также состояния, которые проходит автомат:

а1 а2 а2 а1 а3 а4 а1 а4
q1 q1 q2 q1 q1 q1 q2 q3
b1 b1 b2 b1 b2 b1 b1 b1.

Метки:  

Автомат с памятью. продолжение

Дневник

Среда, 22 Декабря 2010 г. 20:55 + в цитатник
Конечный автомат является абстрактной математической моделью дискретного устройства. Поведение, описанное данной моделью, может быть по-разному реализовано в дискретном устройстве. При синхронной реализации моменты времени, когда определяется состояние, в которое переходит устройство, а в случае автомата Мили и выходной символ, зафиксированы. Технически это осуществляется введением генератора синхронизирующих сигналов, которые инициируют соответствующие действия. Период следования таких сигналов не должен быть меньше чем время, необходимое для завершения переходных процессов в устройстве. Реализованный таким образом конечный автомат называется синхронным автоматом.
При асинхронной реализации указанные моменты времени не фиксированы. Они связаны с моментами, в которые происходит изменение входного сигнала. Реализованный таким образом автомат называется асинхронным автоматом. Если синхронный автомат различает последовательности разной длины из одинаковых входных символов, т. е. может реагировать на них различными выходными последовательностями, то асинхронный автомат воспринимает последовательность одинаковых входных символов любой длины как один символ. В схеме такого устройства генератор синхронизирующих сигналов отсутствует.

Метки:  

Автомат с памятью

Дневник

Среда, 22 Декабря 2010 г. 20:55 + в цитатник
Таблица 18.1
Пример задания комбинационного автомата
Вход Выход
а1

а2


… …

а


Моделью описанного устройства является конечный автомат, представляющий собой совокупность следующих объектов:
А = {a1, a2, … , a} – множество входных символов, или входной алфавит;
В = {b1, b2, … , b} – множество выходных символов, или выходной алфавит;
Q  {q1, q2, … , q} – множество состояний, или внутренний алфавит;
 : A  Q  Q – функция переходов;
 : A  Q  В – функция выходов.

Для конечного автомата используется обозначение (A, B, Q,  ). Слово «конечный» подчеркивает, что все три множества, входящие в состав данной модели, конечны. В том виде, в каком эта модель здесь представлена, она носит название «автомат Мили». Другой разновидностью данной модели является автомат Мура, отличающийся от автомата Мили только тем, что функция выходов не зависит от входного символа, т. е. представляет собой отображение  : Q  В.

Значением функции (a, q) является состояние q+, в которое переходит автомат из состояния q, если на вход его подан символ а. Значением функции (a, q) является выходной символ, выдаваемый автоматом в состоянии q при поступлении на его вход символа а, а значением функции (q) автомата Мура – выходной символ b, который выдает автомат, находясь в состоянии q. Если значения функций (a, q) и (a, q) определены для любой пары значений аргументов а и q, а в модели Мура функция (q) определена для всех значений q, то автомат является полностью определенным, или полным автоматом. Иногда приходится иметь дело с не полностью определенным, или частичным автоматом, у которого эти функции могут быть определены не везде.

Метки:  

 Страницы: [1]