Лекция
Привет, Вы узнаете о том , что такое конечные автоматы, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое конечные автоматы, виды конечных автоматов , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.
Конечный автомат — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно. Триггер является простейшим автоматом. Рассмотрим два наиболее распространенных типа триггеров: RS-триггер и счетный триггер. Состояния этих автоматов являются их выходом, т.е. это автоматы Мура. В RS-триггере два входа: Reset и Set. ВходReset сбрасывает, a Set устанавливает единичное состояние автомата (рис. 5.12а).
а) б)
Рис. 5.12
В счетном триггере (рис. 5.12б) единственный счетный вход переключает автомат из нулевого состояния в единичное и обратно. Подробно аналогичный триггер был описан в разделе 5.2.
Электронные часы являются одним из наиболее широко применяемых в быту электронных приборов, управление которыми построено на основе модели конечного автомата. Простейшие электронные часы обычно показывают время, дату и дают возможность установки времени и даты. Управление этими возможностями производится встроенным автоматным преобразователем, входами которого являются события нажатия внешних управляющих кнопок. Структурная схема электронных часов показана на рис. 5.13
Рис.5.13
У
правляющие кнопки на часах обозначены «а» и «b». Кроме устройства отображения, высвечивающего цифры, а также схемы отображения, преобразующей двоично-десятичные коды цифр в семиразрядный код управления светодиодами, на схеме показаны четыре регистра отображения. Эти регистры хранят двоично-десятичные коды четырех цифр, которые в настоящий момент высвечиваются на циферблате с помощью схемы и устройства отображения. Также показаны комбинационные схемы «ИЛИ», пропускающие любой из разрешенных кодов на регистры отображения и шина «Управление», разрешающая в каждой ситуации выдачу на регистры отображения сигналов либо секундомера, либо часов, либо даты. На схеме также присутствуют регистры секундомера и генератор тиков, который выдает сигнал с частотой 1 Гц.
В последовательностныхавтоматах одна и та же совокупность состояний входных символов может в разные тактовые моменты цикла определять разные состояния выходных функций. Например, на одном из этапов циклаτvпри совокупности входовx1= 1,x2= 0,x3= 0 выходная функцияy1 = 0, а на каком-либо другом этапе циклаτv+iпри такой же совокупности входов выходная функцияy1 = 1.Рис. 5.14
Устройство управления, организующее работу всех элементов электронных часов, построено на основе модели конечного автомата. Граф переходов этого автомата изображен на рис. 5.14. В начальном состоянии отображается время. Это значит, что двоичный код этого состояния (после дешифрирования) открывает выходы четырех двоично-десятичных регистров, хранящих единицы и десятки минут и единицы и десятки часов на входы четырех комбинационных схем «ИЛИ».
Конечный автомат реагирует на событие нажатия кнопки «а» на корпусе часов переходом в состояние «Установка минут», в котором событие нажатия кнопки «b» вызовет увеличение числа, хранящегося в регистрах, отведенных для минут. При этом переносы из регистра секунд и в регистр, отведенный под хранение числа, блокируются. Событие нажатия кнопки «b» в состоянии «Установка месяца» вызовет увеличение числа, хранящегося в регистрах, отведенных для месяца.
Реактивные системы. Следует выделить особый класс систем, который назван «реактивными», или «реагирующими» системами (reactive systems). Это системы, взаимодействующие с окружением и реагирующие на поток внешних событий. Они состоят из нескольких подсистем, и взаимодействие подсистем является частью взаимодействия системы с ее окружением. Микрокалькулятор, электронные часы, система управления проходом в метро – все это реактивные системы. Модель конечного автомата является удобным средством описания таких систем: она обладает ясностью семантики, наглядностью и выразительностью и в то же время достаточно строга и формальна. Однако классическое графическое представление конечных автоматов страдает рядом недостатков. Главным недостатком является отсутствие понятия времени. Об этом говорит сайт https://intellect.icu . Другие недостатки – отсутствие иерархии состояний, обобщения переходов, средств выражения прерываний и продолжения нормальной работы после их обработки.
Простым расширением модели классического конечного автомата является введение понятия «внешнее событие», наступление которого можно считать условием перехода автомата из состояния в состояние. Такими событиями могут быть получение на вход автомата символа или же целого сообщения, прерывание, событие срабатывания таймера. С этим последним типом событий естественно связывается понятие времени в автомате. Действительно, введение понятия времени проще всего связать с ограничением времени пребывания автомата в конкретном состоянии и такое ограничение задать таймером. Событие срабатывания таймера вызовет переход автомата в другое состояние.
Рис.5.15
Рассмотрим в качестве примера задачу спецификации процесса, определяющего одинарный либо двойной щелчок мыши. Двойным щелчком считается пара нажатий на клавишу мыши, разделяемая менее чем τ = 250 мс. На рис. 5.15 представлен граф переходов автомата, решающего эту задачу. По первому щелчку мыши (click) автомат переходит в состояние Q1, и если до истечения τ =250 мс на вход автомата поступит еще один сигнал-событие click, то на выход будет выдан сигнал «double», в противном случае - сигнал «single».
Во многих приложениях обычная модель конечного автомата расширяется путем добавления переменных. Для одной из переменных с конечной областью определения может использоваться специальное название state – «состояние». Возможные состояния такого автомата характеризуются наборами значений всех переменных соответствующей программы. Так достигается соответствие между программным представлением поведения реактивной системы и графическим представлением состояний и переходов.
Еще одним широко применяемым расширением классической модели конечного автомата являются диаграммы состояний(Statecharts), введенные Д. Харелом. Особенностью такой «карты состояний» является наличие гиперсостояния, объединяющего несколько состояний, имеющих идентичную реакцию на одно и то же событие. Управление при возврате в гиперсостояние передается тому состоянию, в котором система находилась последний раз прежде, чем она покинула данное гиперсостояние. Переходы между состояниями в такой модели вызываются либо условиями (наступлением истинности предиката над внутренними переменными автомата, например, условие исчерпания буфера), либо событиями. Событиями в диаграммах состояний являются внешние события автомата. Обычно это прием управляющих или информационных сообщений из окружающей среды.
Рассмотрим в качестве примера использования Statecharts простейший автомат, регулирующий пешеходный переход. Внешние события автомата – это события нажатия пешеходами кнопки-запроса на тротуаре и исчерпание тайм-аута. Автомат естественно строить как автомат Мура, в котором выход – регулирование светофора и разрешающий сигнал на переход – это потенциальные сигналы, являющиеся функциями состояния (рис. 5.16).
Рис. 5.16
Выход автомата в каждом состоянии представляется парой:<Светофор транспорта; светофор пешеходов>. Например, в состоянии Q1 управляющий автомат устанавливает <З;К>, т.е. включенными зеленый свет транспорту и красный – пешеходам; в состоянии Q6 установлен <Ж,К;К>, т.е. желтый и красный свет транспорту (приготовиться) и красный – пешеходам. В начальном состоянии Q0 разрешен проезд транспорту, а пешеходам движение запрещено. В состояниях Q4, Q5 при запрещающем сигнале транспорту зеленый сигнал пешеходам мигает каждые t0 секунд в течение t2 секунд. Запрос на переход принимается только в состоянии Q0, в остальных состояниях он игнорируется. Задержки (тайм-ауты t0 – t3) устанавливаются в момент перехода автомата в данное состояние, по исчерпании тайм-аута автомат переходит в следующее состояние. В гиперсостоянии G, объединяющем пару состояний Q4 и Q5, автомат находится ровно t2 секунд: внутренние переходы не срывают тайм-аута. Именно для этого здесь удобно использовать гиперсостояние G.
Конечный автомат как преобразователь информации является мощной моделью, однако существуют алгоритмические проблемы, которые не могут быть решены с помощью конечного автомата. Одной из таких проблем является проблема умножения двоичных чисел.
Теорема 5.2. Умножение двоичных чисел не может быть выполнено с помощью конечного автомата.
Доказательствотеоремы проведем от противного.
Предположим, что такой конечный автомат существует. Пусть он имеет n состояний. Подадим на вход автомата два одинаковых двоичных числа 2n+1. Каждое из этих входных чисел записывается n+2 двоичными разрядами. Автомат, выполняющий умножение, получает на вход n+1 пар нулей, за которыми следует пара единиц – последовательное представление пары входных аргументов. Автомат, если он существует, должен выдать в качестве результата число 22n+2 , т.е. он должен выдать 2n+2 нуля, за которыми следует единица. Иными словами, после того, как автомат получит n+2 входных сигнала, он, перейдя в автономный режим, должен выдать еще n нулей, за которыми он должен выдать единицу (см. рис. 5.17).
Рис. 5.17
Однако очевидно, что никакой конечный автомат с n состояниями, работая в автономном режиме (т.е. под действием только входных сигналов синхронизации), не может выдать на выход n нулей, за которыми следует единица, так как максимальный цикл в автомате с n состояниями не превышает n.
Невозможность построения конечного автомата для решения этой проблемы является отражением того, что объем информации, которую должен был бы «помнить» такой автомат, неограниченно растет с ростом значений исходных чисел. В то же время для выполнения задачи сложения любых двух двоичных чисел автомату достаточно иметь только два состояния, одно из которых помнит наличие, а другое – отсутствие переноса в следующий разряд.
По способу формирования функций выхода выделяют автоматы Мили и Мура. В автомате Мили функция выходов j определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата, т.е.
Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t]. Функциональная схема не отличается от схемы абстрактного автомата.
Рис. 2. Функциональная схема автомата Мили.
В автомате Мура функция j определяет значение выходного символа только по одному аргументу - состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:
Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t].
Рис. 3 Функциональная схема автомата Мура.
Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:
Потребность такого автомата возникает при формировании автоматных сетей.
Рис. 4. Функциональная схема С-автомата.
Интересно выделить особые классы автоматов, математические модели которых опираются только на два носителя алгебры.
Пусть X=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:
Рис. 5. Функциональная схема порождающего автомата.
Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.
Пусть Y=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:
Рис. 6. Функциональная схема распознающего автомата.
Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (qi[t];xi[t]) и перевод автомата в заключительное состояние qk. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называют распознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.
Пусть Q=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:
Рис. 7. Функциональная схема комбинационного автомата.
Особенностью функционирования такого автомата является отсутствие "памяти", т.е. на каждый символ входного алфавита автомат генерирует символ выходного алфавита без учета состояния автомата. Такие автоматы чаще всего называют комбинационными автоматами.
Анализ данных, представленных в статье про конечные автоматы, подтверждает эффективность применения современных технологий для обеспечения инновационного развития и улучшения качества жизни в различных сферах. Надеюсь, что теперь ты понял что такое конечные автоматы, виды конечных автоматов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория конечных автоматов
Комментарии
Оставить комментарий
Теория конечных автоматов
Термины: Теория конечных автоматов