Что относится к конечному автомату
Перейти к содержимому

Что относится к конечному автомату

Конечный автомат

Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: </p> <p>M = (Q, \Sigma, \delta, q_0, F) » width=»» height=»» />, где:</p> <ul> <li>Q — <i>множество состояний</i> автомата;</li> <li>q<sub>0</sub> — <i>начальное (стартовое) состояние</i> автомата (<img decoding=);

  • F — множество заключительных (или допускающих) состояний, таких что F \subseteq Q ;
  • Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
  • δ — заданное отображение множества Q \times \Sigmaво множество \mathcal <P>(Q)» width=»» height=»» /> подмножеств Q: <img decoding=

    • Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
    • Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

    НКА с e.jpg

    НКА без e.jpg

    Если рассмотреть случай, когда автомат задан следующим образом: </p> <p>M = (Q, \Sigma, \delta, S, F) » width=»» height=»» />, где:</p> <p><img decoding=

    • S — множество стартовых состояний автомата, такое что ;

    Тогда появляется третий признак недетерминизма — наличие нескольких начальных (стартовых) состояний у автомата </p> <p>Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.</p> <p>В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.</p> <h3>Автоматы и регулярные языки</h3> <p>Для автомата можно определить язык (множество слов) в алфавите Σ, который он <b>представляет</b> — так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.</p> <p>Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.</p> <h3>Специализированные языки программирования</h3> <ul> <li>Язык последовательных функциональных схем SFC (Sequential Function Chart) — графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).</li> </ul> <p>В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.</p> <h3>Разработка моделей с использованием конечных автоматов</h3> <p>Конечные автоматы позволяют построить модели систем параллельной обработки, однако, чтобы изменить число параллельных процессов в такой модели требуется внести существенные изменения в саму модель. Кроме того, попытка разработки сложной модели на конечном автомате приведет к быстрому росту числа состояний автомата, что в итоге сделает разработку такой модели крайне утомительным занятием. Как было отмечено выше последнюю проблему можно решить, если использовать недетерминированный автомат.</p> <h3>Примечания</h3> <h3>См. также</h3> <h3>Ссылки</h3> <ul> <li>Конечные автоматы</li> <li>Формальные методы</li> </ul> <p> <em>Wikimedia Foundation . 2010 .</em> </p> <h4>Полезное</h4> <h4>Смотреть что такое «Конечный автомат» в других словарях:</h4> <p><strong>конечный автомат </strong> — КА Вычислительная модель, описывающая автомат с конечным числом состояний. КА широко применяются в программировании, например в лексических анализаторах компиляторов. [http://www.morepc.ru/dict/] конечный автомат Спецификация последовательности… … Справочник технического переводчика</p> <p><strong>Конечный автомат</strong> — математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы. По английски: Finite state machine См … Финансовый словарь</p> <p><strong>конечный автомат</strong> — baigtinis automatas statusas T sritis automatika atitikmenys: angl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. конечный автомат, m pranc. automate final, m; automate fini, m; automate terminal, m;… … Automatikos terminų žodynas</p> <p><strong>конечный автомат в модульном исполнении</strong> — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite modular automaton … Справочник технического переводчика</p> <p><strong>конечный автомат доступности</strong> — (МСЭ Т Y.1711). [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN availability state machineASM … Справочник технического переводчика</p> <p><strong>КОНЕЧНЫЙ АВТОМАТ</strong> — автомат, у к рого множество состояний, а также множество входных и выходных сигналов являются конечными. К. а. может быть моделью технич. устройства (ЭВМ, релейное устройство) либо биол. системы (идеализир. нервная система животного). Важными… … Большой энциклопедический политехнический словарь</p> <p><strong>детерминированный конечный автомат</strong> — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite deterministic automaton … Справочник технического переводчика</p> <p><strong>Конечный автомат с памятью</strong> — Конечный автомат с памятью  математическая модель устройства, поведение которого зависит как от входных условий, так и от предыдущего состояния. Для описания конечного автомата с памятью используются языки операторных схем, регулярных… … Википедия</p> <p><strong>Автомат Мура</strong> — (автомат второго рода) в теории вычислений конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и не зависит напрямую, в отличие от автомата Мили, от входных значений. Автомат Мура назван … Википедия</p> <p><strong>Конечный</strong> — Содержание 1 Конечный 2 Конечная 3 Конечные 4 Фамилия … Википедия</p> <h2>Конечные автоматы в реальной жизни: где мы их используем и почему</h2> <p>Привет, меня зовут Антон Субботин, я выпускник курса «Мидл фронтенд-разработчик» в Яндекс.Практикуме. Не так давно мы с наставником курса Захаром Овчаровым провели вебинар, посвящённый конечным автоматам и их практическому применению. Вебинар получился интересным, а потому по его следам я написал статью для Medium на английском языке. Также есть запись вебинара. Однако мы с Захаром решили сделать ещё кое-что: перевести на русский и немного расширить статью, чтобы вы могли никуда не ходить и прочитать её здесь, на Хабре. Разобрались с предысторией — теперь начнём погружение в мир конечных автоматов.</p> <p><img decoding=

    Конечный автомат с счастливым и грустным Васькой

    Конечные автоматы

    Для начала дадим определение: конечный автомат (finite-state machine, FSM) — это математическая абстракция, модель, которая может находиться только в одном из конечного числа состояний в каждый конкретный момент времени. Автомат умеет переходить из одного состояния в другое в ответ на данные, которые подаются на вход; изменение состояния называется переходом. FSM определяется списком его состояний, начальным состоянием и инпутами, запускающими переходы.

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

    • Состояния. Кот либо счастлив, либо грустен и не может испытывать обе эмоции одновременно.
    • Начальное состояние. Мы предположили, что Васька по умолчанию счастлив.
    • Переходы. Вы можете уйти или прийти, и состояние кота изменится.

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

    Примеры использования

    FSM можно использовать для описания алгоритмов, позволяющих решать те или иные задачи, а также для моделирования практически любого процесса. Несколько примеров:

    1. Логика искусственного интеллекта для игр. Вот статья, раскрывающая эту идею.
    2. Синтаксический и лексический анализ. Подробнее о таком применении можно прочитать здесь. В том числе сюда относится проверка языка — мы собираемся реализовать её в части статьи, посвящённой проверке бинарного кода.
    3. Сложные компоненты. О них есть хорошая статья, однако мы тоже попробуем разобрать эту тему.
    Проверка бинарного кода

    Создадим наш первый автомат. Посмотрите последний пример по ссылке или пишите код по ходу чтения. Будем реализовывать допускающий автомат с конечным состоянием. Это конечный автомат, цель которого — определить, принадлежит ли некая строка определённому языку, и либо допустить, либо отклонить её. Мы уже обсуждали начальное и другие состояния и переходы, однако теперь потребуется определить ещё два параметра:

    • Алфавит. Набор символов, которые должно содержать проверяемое значение (и ни одного символа вне алфавита).
    • Конечные состояния. Подмножество существующих состояний — возможно, пустое. Когда FSM завершает свою работу, он принимает проверяемое значение, если это подмножество включает текущее состояние, и отклоняет в противном случае.
    • Нам нужно создать автомат для проверки случайных значений, который будет отвечать, является ли значение бинарным кодом.
    • Мы принимаем непустые строки с символами 0 и 1 и отклоняем всё остальное.

    Вот наш автомат, детерминированный акцептор с конечным состоянием:

    У нас получился автомат на основе классов, способный проверять случайные значения на соответствие своим определениям. Чтобы использовать его, мы должны создать экземпляр со всеми необходимыми параметрами. Давайте разберёмся.

    • Алфавит. Это очень просто. Мы принимаем только символы 0 и 1.
    • Состояния. Это тоже легко. Значение либо бинарное, либо нет. Мы называем состояния q0 («значение — не бинарный код») и q1 («значение — бинарный код»).
    • Начальное состояние. Мы не принимаем пустую строку, поэтому начальное состояние — q0.
    • Конечные состояния отмечают значение как принятое. В нашем случае единственное подходящее состояние — q1.
    • Переходы. См. диаграмму:

    Схема акцептора бинарного кода

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

    • Если текущее состояние — q0, а текущий символ — 0 или 1, выполнить переход в состояние q1.
    • Если текущее состояние — q1, а текущий символ — 0 или 1, выполнить переход в то же состояние.
    • Если текущий символ не равен 0 или 1, отклонить проверяемое значение независимо от текущего состояния.
    Использование и тестирование

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

    Сложная форма

    Пример с проверкой бинарного кода — довольно тривиальный. Вряд ли вам часто придётся решать такие задачи, если придётся вообще. Давайте рассмотрим ещё один пример — создадим форму с несколькими состояниями в UI-ориентированном FSM. Код автомата доступен на CodeSandbox, вы можете перейти к нему или попробовать написать его самостоятельно.

    Для начала создайте новый проект в React:

    Структура проекта должна выглядеть так:

    App.js и index.js не требуют изменений. FSM.js будет содержать новую реализацию FSM, напишем её:

    Обратите внимание, что мы удалили алфавит и состояния. Теперь у нас есть только два параметра, которые нужно определить:

    • Начальное состояние. Работа FSM должна где-то начинаться.
    • Переходы. Объединяем их с состояниями — так мы создаём более ёмкий экземпляр, при этом обеспечивая ту же функциональность.

    Наша реализация обязывает использовать метод send для изменения состояния. Мы также добавили метод subscribe . Это очень полезно, если мы хотим, чтобы автомат реагировал на изменение состояния.

    Давайте протестируем код на нашем примере с Васькой. Создайте файл test.js :

    Теперь запустите его с помощью node test.js (убедитесь, что вы находитесь в каталоге файлов). Вывод на консоли должен выглядеть так:

    happy
    sad
    happy

    Автомат определённо работает! Наконец, давайте отреагируем на изменение настроения Васьки:

    Запустите автомат снова.

    Васька теперь всегда счастлив, потому что мы не бросаем его. Если после перехода состояние — грустное, срабатывает триггер возвращения, и кот снова счастлив.

    Похоже, всё работает нормально. Переходим к реальной задаче: создадим анкету с несколькими состояниями, которые нужны для управления интерфейсом. Допустим, мы хотим узнать имя и профессию пользователя. Если пользователь — студент, мы спросим, в каком университете он учится. В противном случае спросим, где он работает. Пользователь может вернуться с этапа Education / Work обратно к этапу Personal, на котором мы спрашиваем имя. Наконец, он может отправить анкету при выборе любого из вариантов занятости.

    Небольшая диаграмма, чтобы стало понятнее:


    Автомат, определяющий нашу анкету

    Когда стало ясно, какие состояния у нас есть и как они соотносятся друг с другом, мы можем приступить к работе над проектом. Первое: нужно установить дополнительные зависимости:

    После завершения установки добавляем директорию /components с компонентами внутри. Также мы создаём файл questionnaireMachine.js в директории /src . Теперь структура проекта выглядит так:

    Файл questionnaireMachine.js создаёт и экспортирует экземпляр Questionnaire FSM:

    Questionnaire FSM

    Следующим шагом будет создание презентационного слоя проекта — самой анкеты. Мы разделим его на три отдельных компонента:

    • Анкета. Основной компонент, определяющий последовательность вопросов.
    • Карточка. Многоразовый компонент для отображения части анкеты.
    • Прелоадер. Простая анимированная точка.

    Первое: нам нужно подписаться на изменения состояния конечного автомата. Каждый раз, когда состояние меняется, мы обновляем uiState . Это нужно для вычисления свойства active компонента карточки — именно оно позволяет экземпляру компонента карточки решать, показывать себя или нет.

    Теперь займёмся компонентом карточки:

    Кнопки в нижней части компонента используют указанные действия как listener для события клика. Вот почему мы здесь передаём функции, изменяющие состояние FSM: так компонент анкеты сможет обновить uiState и отобразить нужную карточку.

    Последняя мелочь — компонент прелоадера. Здесь нет ничего интересного, просто анимированная точка:

    Наконец, добавляем анкету в компонент приложения. Корневой компонент со стилями:

    В итоге должно получиться нечто похожее на это. Если да, возрадуйтесь — вы только что создали анкету на основе конечного автомата! Если что-то не работает, сравните свой код с содержимым этой песочнице. У вас наверняка получится наверстать упущенное.

    Анкета, которую мы только что создали, разделена на логический и презентационный слои, поэтому при желании её поведение или внешний вид легко скорректировать. Одну реализацию конечного автомата можно использовать в любом числе компонентов — этот подход обеспечивает предсказуемую и стабильную работу приложения.

    И ещё кое-что. Несмотря на то, что написать собственный FSM с нуля — очень полезный опыт, для рабочих задач я рекомендую использовать готовые библиотеки, например XState. Там есть и подробная документация, и все необходимые инструменты для работы (их, возможно, даже больше, чем нужно).

    Типы конечных автоматов

    Автомат — система механизмов, устройств, в которой полностью автоматизированы процессы получения, преобразования, передачи энергии, материалов, информации Термин "автомат" используется в двух аспектах:

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

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

    Частным и важным случаем автомата выступает цифровой автомат (ЦА), в котором полностью автоматизированы процессы приема, преобразования, хранения и выдачи цифровой информации.

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

    ЦА считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y. Конечный автомат можно поставить в соответствие такому устройству, как компьютер. Компьютер перерабатывает поступающие входные данные в выходные данные (результат), но этот результат соответствует не только входным данным, но и текущему состоянию компьютера, т.е. тем данным, которые хранятся в памяти компьютера, например, результаты предыдущих вычислений, программы вычислений.

    Работа ЦА осуществляется в автоматном времени, определяемом числом периодов поступления входных сигналов.

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

    Слова входного языка можно представить символами множества X=1,x2. xn>, который называют входным алфавитом, а слова выходного языка — символами множества Y=1,y2. yp>, который называют выходным алфавитом. Множество состояний автомата S=1,s2. sm> называют алфавитом состояний.

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

    Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i-того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов.

    Понятие «состояние» используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов и/или слов выходного языка от символов и/или слов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] на выходе устройства генерируется символ yÎY. Эту зависимость определяет функция выходов автомата j. Для каждого текущего состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] автомат переходит в очередное состояние sÎS. Эту зависимость определяет функция переходов автомата y. Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (s1[[1]s2[2]s3[3]. ) и последовательности выходных символов (y1[1]y2[2]y3[3]. ), которые для последовательности символов (x1[1]x2[2]x3[3]. ) разворачиваются в моменты дискретного времени t = 1,2,3. В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках — последовательности символов алфавитов X, Y и S.

    Итак, математическая модель конечного автомата есть трехосновная алгебра, носителями которой являются три множества X, Y и S, а операциями — две функции j и y:

    где X=1;x2;. xn > множество символов входного алфавита;
    Y=1;y2;. yp > множество символов выходного алфавита;
    S=1;s2;. sm> множество символов состояний автомата;
    y: (SÄX) ® S функция переходов автомата для отображения пары (s;x) текущего момента дискретного времени [t] в состояние s очередного момента дискретного времени [t+1];
    j: (SÄX) ® Y функция выходов автомата для отображения пары (s;x) текущего момента дискретного времени [t] в символ y выходного канала этого же момента дискретного времени [t].

    Так как области определения функций переходов и выходов совпадают, то обобщенный оператор поведения автомата можно представить так:

    Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:

    Если на входе автомата имеем слово a = (x1x2x3. xn), то, считывая последовательно символы этого слова, на выходе автомата генерируется последовательность символов слова b по следующей схеме:

    Так как на каждом i-ом такте к слову длины (i-1) приписывается справа очередной символ j(s[1];x1[1]x2[2]. xi[i]), то последовательность символов выходного слова можно записать так:

    Если считывание символов входного слова a выполняется последовательно слева направо, то всегда найдется такая последовательность (x1x2. xn-1)=g, для которой

    Поэтому если входное слово a = (gxn), то выходное слово b можно записать так:

    Это означает, что последний символ слова b есть результат работы автомата, начавшего работу в состоянии s и считавшего последний символ слова a, но значение этого символа зависит от всей входной последовательности.

    Длина выходного слова всегда равна длине входного слова.

    Изменение состояний автомата для последовательности символов слова a = (x1x2x3. xn) может быть описано следующей схемой:

    где s[1] — начальное состояние автомата.

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

    Если входное слово a = (gxn), то изменение состояния автомата может быть описано так:

    Это означает, что s[n+1] есть последнее состояние автомата, начавшего работу в состоянии s и считавшего последний символ слова a в момент дискретного времени n.

    Если функции переходов и выходов однозначно определены для каждой пары (s;x)Î(SÄX), то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определенным.

    Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным.

    Если у автомата задано начальное состояние s=s0ÎS, в котором он находится всегда до приема первого символа входного слова, то автомат называют инициальным. В этом случае модель автомата записывают так:

    Последовательность символов в слове b и последовательность состояний автомата s однозначно определяются начальным состоянием автомата s=s0 и последовательностью символов во входном канале a. Поэтому отображение входного слова a на выходное слово b чаще называют автоматным отображением, то есть b = М(s0;a), а М – автоматным оператором.

    Автоматное отображение обладает свойствами:

    1) входное и выходное слова имеют одинаковую длину (свойство сохранения длины);

    2) yi-ый символ выходного слова зависит от всей последовательности символов входного слова, до xi-го включительно; кроме того если a=a1a2, то b=b1b2..

    Задание конечного автомата:

    Для описания (задания) ЦА используются разнообразные средства, называемые языками, которые делятся на начальные и автоматные языки. Поскольку языки базируются на алфавитах, то применительно к ЦА множество Х трактуется в качестве входного алфавита, множество Y — выходного алфавита, а множество S — внутреннего алфавита. Как и для других объектов, для автоматов используются разные таблицы, матрицы, графы.

    Наиболее общее при выработке выходных сигналов, формировании новых состояний под действием входных сигналов отражается законом функционирования автомата [4, 12]:

    s(t)= d (s(t-1), x(t)),

    y(t)= l (s(t-1), x(t)).

    Как видно, закон функционирования представляет собой совокупность двух функций: функции перехода d и функции выхода l.

    В формулах используются обозначения:

    t — данное автоматное время, t-1 — предыдущее автоматное время, d — оператор формирования данного состояния s, l — оператор формирования данного выходного сигнала y, х — входной сигнал.

    Видно, что данное состояние s(t) зависит от предыдущего состояния s(t-1) и входного сигнала в данный момент времени, что выходной сигнал в данный момент времени так же определяется предыдущим состоянием и входным сигналом в данный момент времени.

    Автомат задан, если заданы:

    1. Конечное множество входных сигналов, заданных с помощью входного алфавита X=1, x2,…, xm>

    2. Конечное множество выходных сигналов, заданных с помощью выходного алфавита y=1, y2 . yn>

    3. Конечное множество состояний автомата заданного с помощью алфавита S=1,s2. sm>

    4. Начальное состояние автомата

    5. Функция выходов, определяющая зависимость выходного сигнала и состояния автомата y[kt]=fв(U[kt], a[kt]) где t – длительность такта k – номер такта. Конечный автомат существует в конечном (дискретном) времени.

    6. Функция переходов

    Функция выходов и функция переходов является характеристическими функциями.

    Таким образом, в определении конечного автомата фигурирует три множества и две функции M=в, fп>

    Функция перехода fп:X*S S Функция выхода fв:X*S Y

    Операторы, описывающие работу автомата, обычно задают таблицей переходов и таблицей выходов.

    В таблице переходов показывают в какое состояние попадает автомат от того или иного входного сигнала. В таблице выходов показывают какой выходной сигнал генерирует автомат в зависимости от типа входного сигнала и текущего состояния автомата.

    К примеру, рассмотрим таблицы переходов и выходов некоторого автомата.

    Таблица переходов автомата

    Входной сигнал Состояние
    a0 a1 a2 a3
    x1 a1 a2 a3 a3
    x2 a0 a0 a0 a0

    Таблица выходов автомата

    Входной сигнал Состояние
    a0 a1 a2 a3
    x1 y2 y2 y1 y2
    x2 y2 y2 y2 y3

    В клетку таблицы переходов, находящуюся на пересечении столбца с буквой аi и строки с буквой xj, записывается состояние автомата, в которое он переходит из состояния аi при подаче на вход сигнала xj. В аналогичную клетку таблицы выходов записывается выходной сигнал yi, который формируется автоматом при таком переходе.

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

    Таблица переходов и выходов автомата

    Выходной сигнал Cостояние
    a0 a1 a2 a3
    x1 a1 y2 a2 y2 a3 y1 a3 y2
    x2 a0 y2 a0 y2 a0 y2 a0 y3

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

    Граф автомата состоит из узлов, соединенных ветвями. Узлы (кружки на схеме графа) отождествляют внутренние состояния автомата. Каждая ветвь графа, т.е. ориентированная линия, стрелка которой указывает следующее состояние автомата, отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе. Входной и соответствующий ему выходной сигналы разделяются на чертеже запятой или косой чертой. Если некоторый входной сигнал не меняет состояния автомата, то соответствующая ветвь замыкается на кружке (узле), из которого она выходит.

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

    Типы конечных автоматов

    1) по закону функционирования ЦА делятся на автоматы 1-го рода (автоматы Мили) и ЦА 2-го рода. Последние автоматы в случае, когда нет явной зависимости от входных сигналов x(t), являются автоматами Мура. Видимо, целесообразнее по первому критерию автоматы делить на автоматы Мили и Мура;

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

    Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t].

    Рис. 1.3. Функциональная схема автомата Мили.

    В автомате Мура функция j определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:

    Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t].

    Рис. 1.4. Функциональная схема автомата Мура.

    2) по конечности множеств X, Y, и S автоматы бывают конечными и бесконечными. Может быть, данный критерий стоит трактовать как критерий по мощности ЦА;

    3) по объему памяти автоматы делятся на автоматы с памятью (последовательностные автоматы) и автоматы без памяти (логические комбинационные схемы);

    4) по степени раскрытия структуры автоматы бывают абстрактными автоматами (детали структуры не раскрыты) и структурными автоматами (раскрыты детали структуры);

    5) по отношению между автоматами среди автоматов можно выделить подавтоматы, надавтоматы. Если, например, известно, что ЦАА < ЦАВ, то автомат А является подавтоматом автомата В, а автомат В — надавтоматом автомата А;

    6) по полноте используемых переходов автоматы делятся на полностью определенные автоматы и частично определенные автоматы;

    7) по стабильности периода следования входных сигналов автоматы бывают синхронными автоматами (период следования входных сигналов- постоянная величина) и асинхронными автоматами (период — переменная величина);

    8) по вероятности переходов автоматы делятся на детерминированные (не вероятностные) и недетерминированные (вероятностные) автоматы;

    9) при нулевой мощности множества внутренних состояний (| S |= 0) автомат называется автономным, при | Y | = 0 — автоматом без выхода. Если среди состояний автомата выделяется начальное состояние s0, то автомат называется инициальным;

    10) по применению автоматы можно разделить на автоматы:

    а) промышленные (сварочные, кузнечно-прессовые, литейные, строительные, транспортные, упаковочные роботы, контрольные, диагностические и др.);

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

    в) торговые (газетные, упаковывающие, взвешивающие и др.);

    г) учебные (обучающие, тестирующие, моделирующие, демонстрирующие и др.);

    д) медицинские (искусственные органы, хирургические, диагностирующие, дыхательные, тренирующие и др.);

    е) информационные (видеомагнитофоны, системы "вопрос — ответ" и др.).

    Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:

    Рис.1. 5. Функциональная схема С-автомата.

    Интересно выделить особые классы автоматов, математические модели которых опираются только на два носителя алгебры.

    Пусть X=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

    Функциональная схема автомата приведена на рис.1.6.

    Рис.1.6. Функциональная схема порождающего автомата.

    Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.

    Пусть Y=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

    Функциональная схема автомата приведена на рис.1.7.

    Рис. 1.7. Функциональная схема распознающего автомата.

    Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (qi[t];xi[t]) и перевод автомата в заключительное состояние qk. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называют распознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.

    Пусть Q=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

    Функциональная схема автомата приведена на рис.8.

    Рис. 1.8. Функциональная схема комбинационного автомата.

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

    Автоматы, выполняющие роль "0" и

    "1" в алгебре автоматов. С — автомат

    Любая алгебра должна иметь конструкции, выполняющие в ней роль "0" и "1". По аналогии с алгеброй алгоритмов роль "0" выполняет пустой автомат (ноль-автомат), ЦА0. Пустой автомат – это автомат, в котором запрещены всевозможные переходы. Естественно, что ЦАА \/ ЦА0 = ЦАА, ЦАА /\ ЦА0 = ЦА0.

    Роль "1" возлагается на полный ЦА (ЦА1), в простейшем случае такой автомат представляет собой настраиваемое объединение рассматриваемых автоматов. Естественно, что ЦАА \/ ЦА1 = ЦА1, ЦАА /\ ЦА1 = ЦАА, дополнение ЦА1 = ЦА0, дополнение ЦА0 = ЦА1.

    Что относится к конечному автомату

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

    Что такое автомат?

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

    Схема

    У этого автомата есть:

    • два состояния (“свет выключен”, “свет включён”)
    • два перехода между этими состояниями
    • одно событие “нажали кнопку”, которое вызывает оба перехода
    • псевдопереход от чёрного кружка с заливкой, показывающий, какое состояние будет начальным. Конечного состояния здесь нет (иначе оно было бы помечено псевдопереходом к чёрному кружку без заливки)

    Чуть более сложный автомат для разбора числа с плавающей точкой показан ниже:

    Схема

    Оба этих автомата являются детерминированными, потому что входной символ или событие однозначно определяет переход, и нет “самопроизвольных” переходов при отсутствии события. Если эти условия не соблюдаются, автомат становится недетерминированным. Также автомат не является детерминированным, если он использует дополнительную память (например, стек ранее накопленных символов) для принятия решения о переходе.

    Детерминированный и недетерминированный конечные автоматы

    Детерминированный конечный автомат может разобрать строку в один проход из начала в конец, не используя дополнительной памяти кроме заранее заданных таблицы состояний и таблицы переходов между состояниями по событиям. В этой предсказуемости и линейной сложности разбора строки его главное преимущество. Например, в конце разбора строки автомат лексического анализатора приходит в состояние accepted либо в состояние error, что означает успешный или неуспешный разбор строки на токены соответственно.

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

    Существует формальный алгоритм превращения недетерминированного автомата без дополнительной памяти в детерминированный. Кстати, подобные алгоритмы используют реализации библиотек регулярных выражений: например, для выражения «([a-z])|([a-z]\(\))» легко составить недетерминированный автомат с неоднозначными или пустыми переходами, а алгоритм позволяет превратить его в детерминированный.

    Регулярное выражение в ДКА

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

    • Символ * задаёт итерацию (a.k.a. замыкание Клини)
      • Пример: “1*” ищет строки “”, “1”, “11”, …
      • Пример: “ab” ищет подстроку “ab”, “ab*” ищет подстроки вида “a”, “ab”, “abb”, …
      • Пример: “a b c d” ищут подстроки “a”, “b”, “c”, “d”

      Мы построим детерминированный конечный автомат на основе заданного регулярного выражения. Пусть дано выражение «xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)» , построим для него диаграмму автомата. Для наглядности обозначение начальных и конечных состояний убрано — мы считаем, что любой неожиданный символ переводит в состояние ошибки.

      Схема

      Преобразуем конкатенацию с (x | y*) :

      Схема

      Схема

      Схема

      Получаем промежуточный εНКА, т.е. НКА с “пустыми” — или “самопроизвольными” — переходами:

      Схема

      Убираем переходы по пустой цепочке ε:

      Схема

      Теперь состояния s3 и s5 оказались эквивалентны. Уберём s5, переименуем s6->s5, s7->s6.

      Схема

      Убираем неопределённые переходы из НКА:

      Схема

      Теперь p1 и p5 эквивалентны. Уберём p5, переименуем p6->p5, p7->p6.

      Схема

      Полученный автомат эквивалентен выражению «xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)» .

      • он допускает “aaax”
      • он не допускает “xyyb”

      Применение конечных автоматов

      Существует классификация программ по принципам их работы. Один из вариантов – это классификация Д. Харела, которая делит программы на три вида

      • Трансформирующие системы только трансформируют данные, то есть работают в пакетном режиме
      • Реактивные системы ещё и реагируют на команды или события
      • Интерактивные системы реагируют на команды или события и делают ответное воздействие

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

  • Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *