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


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


Способы задания конечного автомата

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

Конечным автоматом называется система <X, Y, Q, Y, Q>, в которой X и Y являются конечными входным и выходным алфавитами, Q - конечным множеством внутренних состояний, Y(x, q) - функцией переходов и Q(x,q) - функцией выходов.

Как указывалось ранее, Y(x,q) задает порядок преобразования входных символов и состояния автомата на предыдущем такте в состояние на последующем, a Q(x,q) - преобразования входных символов и состояния автомата на текущем такте в выходной символ. Если q0 - начальное состояние автомата, а i - номер такта, то его работа описывается системой:

Данные соотношения получили название системы канонических уравнений конечного автомата. Пользуясь ими можно, начиная с q0, последовательно находить все последующие состояния автомата и выходные символы.

Выделяются два типа автоматов - инициальные и неинициальные. В инициальных автоматах начальное состояние фиксировано (т.е. они всегда начинают работать из одного и того же состояния q0). В неинициальных автоматах в качестве начального состояния может быть выбрано любое из множества Q; этим выбором определяется дальнейшее поведение автомата.

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

В табличном способе автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей переходов и матрицей выходов. В этих таблицах строки обозначаются буквами входного алфавита, а столбцы - буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата). В матрице переходов на пересечении строки (xk) и столбца (qr) помещаются значения функции Y (qr, xk), а в матрице выходов - значения функции Q(qr, xk).





 

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

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

Пример 4.3

Модели проверяемые и непроверяемые

Особенности устройств хранения информации

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

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

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

 
 

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