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

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

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

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

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

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

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

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

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

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

Детерминированный конечный автомат может разобрать строку в один проход из начала в конец, не используя дополнительной памяти кроме заранее заданных таблицы состояний и таблицы переходов между состояниями по событиям. В этой предсказуемости и линейной сложности разбора строки его главное преимущество. Например, в конце разбора строки автомат лексического анализатора приходит в состояние 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”

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

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

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

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

  Конечные автоматы (finite-state machine)

  Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рас­суждения и легкость программной или аппаратной реализации.

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

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

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

  • По горизонтали вверху находятся возможные входные символы.
  • По вертикали слева находятся текущие возможные состояния.

  Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.

  Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

  Стартовое состояние — состояние откуда КА начинает свою работу.

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

  Детерминированные конечные автоматы (deterministic finite automaton)

  Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.

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

  

  Здесь изображена диаграмма переходов для ДКА, визуализация примера 1. Состояние 3 является заключающим. По диаграмме видно, что ДКА принимает цепочку символов только в том случае, если будет последовательность из символов ‘a’, ‘b’ и ‘c’.

  Недетерминированные конечные автоматы (nondeterministic finite automaton)

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

  Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.

  Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.

  Множества состояний — в один момент времени НКА может находится в нескольких состояниях.

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

  

  В стартовом состоянии у нас текущим состоянием является <1>, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество <1, 2>.

  Свободным переходом обозначается пунктирной линией.

  

  Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии <2, 4>.

  Для преобразования НКА в ДКА используется алгоритм Томпсона.
  При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.

  Конечные автоматы с магазинной памятью (pushdown automaton)

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

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

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

  Добавление символов в стек — при любом переходе решает какие символы добавить в стек.

  • Детерминированные — к нему применяются те же правила как к ДКА к тому же завершает работу только в заключительном состоянии.
  • Недетерминированные — к нему применяются те же правила как к НКА к тому же он может завершать работу в заключительном состоянии или когда стек станет пуст.

  Шаблон: входной_символ; удаляемый_символ/добавляемый символ. На дно стека добавляется символ $ для, того, что понять когда он закончился.

  

  Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.

  ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.

  Машина Тьюринга (Turing machine)

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

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

  Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.

  

  Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.

  1. Если находится в состоянии 1 и прочитан нуль, записать еди­ницу, сдвинуть вправо и перейти в состояние 2.
  2. Если находится в состоянии 1 и прочитана единица, записать нуль, сдвинуть влево и перейти в состояние 1.
  3. Еcли находится в состоянии 1 и прочитан пустой квадратик, записать единицу, сдвинуть вправо и перейти в состояние 2.
  4. Если находится в состоянии 2 и прочитан нуль, записать нуль, сдвинуть вправо и остаться в состояние 2.
  5. Если находится в состоянии 2 и прочитана единица, записать единицу, сдвинуть вправо и остаться в состояние 2.
  6. Если находится в состоянии 2 и прочитать пустой квадратик, записать пустой квадратик, сдвинуть влево и перейти в состоя­ние 3.

  ДМТ эквивалентен НМТ, так, что они тоже не различаются.

  Универсальная машина Тьюринга (universal Turing machine)

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

  31.Конечные автоматы. Основные определения. Способы задания автоматов.

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

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

  Q — конечное множество состояний автомата;

  q₀ — начальное состояние автомата ( );

  F — множество заключительных (или допускающих) состояний, таких что ;

  Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

  δ — заданное отображение множества во множество подмножеств Q:

  (иногда δ называют функцией переходов автомата).

  Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

  Способы описания:

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

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

  Детерминированность: Конечные автоматы подразделяются на детерминированные и недетерминированные.

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

  Недетерминированный конечный автомат (НКА) является обобщением детерминированного.

  Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации. В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

  Детерминированным конечным автоматом называется произвольная пятерка <Q,Z,b,s,F> , такая что Q и Z — конечные множества, Пусть M = <Q,Z,b,s,F> — детерминированный конечный автомат. Множество Z называется алфавитом автомата M ( автоматы являются устройствами для распознавания языков; если автомат служит для распознавания языка некоторого алфавита Z, то то же самое Z будет алфавитом этого автомата). Множество Q называется множеством состояний автомата M, а элементы этого множества — состояниями. Поскольку в определение автомата входит s — элемент Q, то множество состояний не может быть пустым. Сам элемент s из опре- деления M называется начальным состоянием автомата M. Множество F называется множеством конечных состояний автомата M, а его элементы — конечными состояниями. Наконец, b называется функцией переходов; если для q1, q2 принадл Q и a принадл Z q2 = b(q1; a), то мы говорим, что автомат M переходит из состояния q1 в состояние q2 под действием символа a.

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

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

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

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

• F — множество заключительных (или допускающих) состояний, таких что ;
• Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
• δ — заданное отображение множества во множество

  

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

  

  

  Если рассмотреть случай, когда автомат задан следующим образом:

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

  Тогда появляется третий признак недетерминизма — наличие нескольких начальных (стартовых) состояний у автомата Что такое атомная энергетика

• Инверторный генератор или обычный что лучше для сварки
• В чем нельзя хранить продукты
• Как пользоваться мультиваркой мулинекс