Студопедия
Обратная связь


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram 500-летие Реформации

Загрузка...

Пример 9.2.

По заданному табличному представлению автомата построить систему его команд.

Пусть конечный автомат имеет алфавиты X = {a, b}, Y = {а, b, с}, Q = {1, 2, 3}, а автоматные функции задаются таблицами:

Представленные две таблицы можно объединить в одну, условившись в каждую клетку на первую позицию ставить значение Y(qr, xk), а через запятую на вторую позицию помещать значение Q(qr, xk). В результате получится следующая «сводная» таблица:

Видно, что таблица стала весьма напоминать таблицу, задающую функциональную схему машины Тьюринга (см. п.7.3.3). Из нее легко просматриваются команды преобразования, осуществляемые данным автоматом:

Пусть на начальном такте автомат находится в состоянии q0 = 1 и на его вход в последующие такты подается последовательность abb. Пользуясь перечнем команд можно установить, что автомат преобразует эту последовательность в bсс и при этом окажется в состоянии 3.

Другой вариант описания автоматных функций - графический. Он обладает большей наглядностью, чем табличный. Состояния автомата <X, Y, Q, Y, Q> задается посредством ориентированного графа, который называется диаграммой (точнее, диаграммой Мура). Вершины графа помечены символами из алфавита состояний автомата Q, а каждой команде qixr → qjys соответствует ребро, идущее из вершины qi в вершину qj, при этом ребру приписывается метка xrys. Таким образом, ребро возникает в том случае, если автомат, находящийся в состоянии qi, посредством некоторого входного сигнала xr может быть переведен в состояние qj. Если такой перевод возможен при нескольких входных воздействиях (хг)(1)..... r)(п), и при этом формируются выходные сигналы (ys)(1),..., (ys)(п), то ребру приписывается выражение ((хr)(1), (ys)(1)) v ((хr)(2), (ys)(2)) v...v((xr)(n),(ys)(n).

Для диаграмм, представляющих конечный автомат, справедливы следующие утверждения:

1. из одной вершины не может выходить двух ребер с одинаковым входным символом (условие однозначности);

2. если при работе автомата реализуется входная комбинация qixr, то обязательно существует ребро, идущее из вершины qi помеченное символом хr (условие полноты);

3. количество вершин и ребер диаграммы является конечным.





 

Читайте также:

Раздел 1. ТЕОРИЯ ИНФОРМАЦИИ

Контрольные вопросы и задания

При прочих равных условиях наибольшую энтропию имеет опыт с равновероятными исходами.

Условная энтропия

Пример 9.4

Вернуться в оглавление: Теоретические основы информатики

Просмотров: 1564

 
 

54.166.157.192 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам.