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

Теория автоматов, конечные автоматы

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

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

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

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

Широко применяется аппарат математической логики, алгебры, теории вероятностей, комбинаторики и теории графов.

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

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

Другое направление, называемое абстрактной теории автоматов, изучает поведение автоматов (т. е. характер осуществляемого ими преобразования информации) при отвлечении от специфики их внутреннего устройства и возникло в 1950-х гг.

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

Наиболее изученными являются детерминированные машины (автоматы), к которым относятся конечные автоматы — главный объект изучения в теории автоматов.

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

Термины «последовательностная машина», «автомат Мили», «автомат Мура» употребляются в литературе (причем не одинаково всеми авторами) как синонимы термина «конечный автомат» либо для подчеркивания тех или иных особенностей в функциях перехода конечного автомата.

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

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

Так, например, обстоит дело в задачах с экспериментами над автоматами (работы Э. Ф. Мура и др.), в которых по результатам экспериментов получаются те или иные сведения о функциях перехода автомата или об его объеме памяти.

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

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

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

1) выясняют, существует ли такой конечный автомат, что осуществляемое им преобразование информации удовлетворяет этому условию;

2) если да, то строят функции перехода такого конечного автомата или же оценивают его объем памяти.

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

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

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

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

Разработано много методов синтеза в зависимости от типа схем и от преобразования информации, для реализации которого они предназначены (Синтез релейных устройств).

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

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

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

Изменение состояний входа и внутренних элементов происходит в дискретные моменты времени, интервалы между которыми называются тактами. Внутреннее состояние (состояние внутренних элементов) в конце такта полностью определено внутренним состоянием и состоянием входа в начале такта.

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

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

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

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

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

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

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

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

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

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

С чем едят конечный автомат

Машина Тьюринга и машина состояний, детерминированный и недетерминированный конечный автомат, конечный автомат Мура и конечный автомат Мили. Голова кругом от всех этих понятий. Как во всем этом разобраться новичку? Тем более, что и у бывалых спецов бывает такая каша в голове из этих понятий. Чего только стоит вебинар от Яндекс Практикум на тему «Конечные автоматы в реальной жизни». Именно случайный просмотр этого вебинара сподвиг меня написать статью. Я обратил внимание, что даже более опытные лекторы ловко жонглируют всеми этими понятиями или подменяют одни другими в своих лекциях. С этим можно просто смириться, или дойти до безумия, разбираясь что к чему. И как со всем этим жить начинающему ардуинщику, если про конечные автоматы в программировании трубят из каждого утюга, а добраться до истины самостоятельно непросто?

Не гарантирую, что после прочтения статьи все сразу станет на свои места, но, как минимум, постараемся выудить из всей этой «каши» что-то полезное для себя. Так что усаживайтесь по удобнее, тема не простая, под катом будет много текста.

❯ Во всем виноваты математики

Да, именно так. Математика — это наука с долгой историей. Наука очень увлекательная, и поэтому она затягивает все большее количество умов. И каждому математику в душе хочется стать новым Пифагором, Евклидом, Лобачевским. А для этого необходимо постоянно расширять поле деятельности. Как только появляется какое-то новое научное направления, математики тут же жадно накидываются на него и изобретают свои новые теории.

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

Такая же участь ждала и электронику на заре ее развития. На ранних парах электроника была нераздельно связана со словом «радио» (радиоэлектроника), и ориентирована на радиосвязь. Новое прикладное применение обрела для себя тригонометрия, подтянулась теория сигналов, преобразования Фурье и еще много чего интересного.

❯ Комбинационные логические схемы

С развитием электроники от нее стали откалываться новые направления. Одно из таких — вычислительная техника. И тут математики тоже не остались в стороне. Хорошим подспорьем стала дискретная математика, от которой перешли к математической теории вычислительной техники.

К компьютерам вычислительная техника пришла далеко не сразу. Сперва появились комбинационные логические схемы. К таким схема можно отнести знакомые всем базовые логические вентили НЕ, И, ИЛИ, Исключающее ИЛИ и другие их комбинации. Шифраторы и дешифраторы можно считать более сложным вариантом комбинационных схем.

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

❯ Последовательностные логические схемы

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

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

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

❯ Конечный автомат Мура и Мили

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

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

Частным случаем этой теории являются автоматы Мура и Мили, позволяющие описать функционирование цифровых систем, которые нашла широкое применение для синтеза сложных последовательностных схем на основе ПЛИС. А математические «иероглифы», которыми обильно сдобрена теория, стали хорошим подспорьем для языков описания аппаратуры подобных SystemVerilog или VHDL.

Автоматы Мура и Мили названы в честь своих изобретателей, ученых, разработавших теорию автоматов и математическую базу для них в фирме Bell Labs.

Эдвард Форест Мур (1925–2003) опубликовал свою первую статью «Gedankenexperiments on Sequential Machines» («Мысленные эксперименты с последовательностными автоматами») в 1956 году.

Джордж Мили (1927–2010) опубликовал «Method of Synthesizing Sequential Circuits» («Метод синтеза последовательностных схем») в 1955 году. Впоследствии он написал первую операционную систему для компьютера IBM 704. Позже он перешел на работу в Гарвардский Университет.

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

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

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

Основная разница между конечными автоматами Мура и Мили в том, что у автомата Мура обычно больше (Moore – more) состояний, чем у автомата Мили, решающего ту же задачу.

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

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

❯ Машина Тьюринга

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

Машина Тьюринга была предложена для формализации понятия алгоритма, и является расширением или частным случаем конечного автомата. Сам Алан Тьюринг использовал понятие «вычислительная машина» («computing machine»).

Отдельно останавливаться на самом Тьюринге нет смысла, личность его достаточно известна. Чего стоит только один фильм «Игра в имитацию» с великолепным Бенедиктом Камбербэдчем. Кто не смотрел — крайне рекомендую.

Машина Тьюринга разрабатывалась для того, чтобы ответить на вопрос: «есть ли конкретный метод или механический процесс, который можно применить к математическому утверждению и он ответит, доказуемо ли это утверждение» — которым задавался известный математик Макс Ньюман на своих лекциях в Кембридже.

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

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

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

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

❯ Конечные автоматы в программировании

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

Идея рассматривать программу в терминах конечного автомата сама по себе не новая. Но наиболее активно свое развитие она получила в начале 90-х годов прошлого века. Одним из основоположников данной идеи является профессор Университета ИТМО Анатолий Абрамович Шалыто. Идея заключается в том, чтобы программировать с использованием понятия «состояние». Сперва для названия этого подхода появился термин «Switch-технологии«, так как операторы множественного выбора в традиционных языках подходили для смены состояний программы больше всего. Позже, в конце 90-х термин «Switch-технологии» был заменен на «автоматное программирование«.

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

Автоматное программирование можно рассматривать как самостоятельную парадигму. Есть мнение, что оно должно исправить недостатки ООП, и может использоваться как дополнение к нему.

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

Хочу заметить, что в англоязычном интернете упоминаний о работе Шалыто я не нашел. А Finite State Machine рассматривается как модель для разработки и электрических схем и программных алгоритмов. Каких-то отдельных названий для программирования конечных автоматов я тоже не встречал, обычно так и пишут: «программирование конечного автомата«. Хотя, мне лично такое название, как «автоматное программирование«, кажется удобным для обращения. На Хабре есть интересная статья, посвященная работе Анатолия Абрамовича, советую почитать.

Но, несмотря на всю неоднозначность, все же рекомендую ознакомиться с работами Шалыто, в частности с его книгой «Автоматное программирование«. В ней содержится много полезных прикладных решений. Еще есть сайт автора на эту тему.

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

Хорошим примером языка программирования, специализированного на автоматном стиле, является язык последовательных функциональных схем SFC (Sequential Function Chart).

SFC — язык программирования стандарта IEC61131-3, предназначенный для программирования промышленных контроллеров. Широко используется в SCADA/HMI пакетах для программирования промышленных логических контроллеров PLC. Является графическим языком, программа описывается в виде схематической последовательности шагов, объединенных переходами, подобно диаграмме состояний.

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

❯ Заключение

И все-таки, почему же с конечными автоматами получается такая каша? Мне кажется, что это связано с большим объемом знаний по данной тематике. Не все они имеют прямое отношение к программированию. Да и такая высокая формализация в программировании, как в синтезе электрических схем, скорее всего не нужна. Или все-таки нужна, но программисты обычно не уделяют этому вопросу достаточного внимания?

В общем, можно говорить о том, что такие понятия как: конечный автомат или конечный автомат состояний, и машина состояний или State Mashine, или Finite State Machine (FSM)- являются синонимами. Это связанно с особенностями терминологии на русском и английском языках.

Надеюсь, что дальнейшее изучение теории цифровых автоматов станет для вас значительно проще.

• timeweb_статьи
• конечный автомат
• автомат Мура и Мили
• finite state machine
• FSM
• математика
• логические схемы
• радиоэлектроника
• Тьюринг
• scada разработка программирование

Конечный автомат — JS: Автоматное программирование

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

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

В первую очередь необходимо обратить внимание на то, что finite-state machine появляется только там, где есть процесс. Возьмём пример с Хекслета. Сущность «курс» участвует в процессе публикации на сайте. Сначала курс не виден, но потом мы его публикуем, и он становится доступным на сайте. При этом, у нас есть возможность произвести обратное действие. Этот же курс участвует и в другом процессе, который можно назвать «завершённость». Наши курсы могут появляться на сайте до того, как мы их запишем до конца. В какой-то момент курс наполняется всеми уроками, и мы переводим конечный автомат в положение «завершён». Получается, что одна и та же сущность участвует, как минимум, в двух процессах. И каждый обладает своим собственным конечным автоматом.

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

В определении уточняется, что состояния должны быть дискретными. Другими словами, мы должны иметь возможность проводить чёткие различия между разными состояниями процесса. Процесс нагрева воды нельзя представить как конечный автомат, если мы не выделим в нём конкретные точки (состояния): например, тёплая вода (50 градусов), горячая вода (80 градусов) и холодная вода (10 градусов).

И последнее. Что значит «управляющие состояния»? Понятие состояния не является чужеродным для мира программирования. В одной из первых лекций я рассказывал о том, что состояние программы это, грубо говоря, слепок её памяти. Другими словами, значение всех переменных в конкретный момент времени. Это действительно так, но можно пойти ещё дальше и заметить, что состояние можно поделить на два типа. Первый тип — это состояние, отвечающее за все возможные пути движения данных сквозь программу. Второй — это данные сами по себе или так называемое вычислительное состояние.

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

Управляющие состояния	Вычислительные состояния
Их число не очень велико	Их число либо бесконечно, либо конечно, но очень велико
Каждое из них имеет вполне определённый смысл и качественно отличается от других	Большинство из них не имеет смысла и отличается от остальных лишь количественно
Они определяют действия, которые совершает сущность	Они непосредственно определяют лишь результаты действий

Рассмотрим простейший конечный автомат на примере телевизора и процесса включения. В этом процессе участвуют два состояния «включен» и «выключен», которые меняются по событиям «включить» и «выключить».

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

Этот автомат описывает процесс приготовления кофе в кофемашине. Не так тривиально как с телевизором.

Что ещё может быть описано конечным автоматом?

• Состояние заказа
• Светофор
• Активация Сим-карты
• Запуск практики на Хекслете
• Пользовательские интерфейсы (UI)

Лично мне кажется, что проще перечислить то, что не описывается конечным автоматом, чем наоборот.

Вывод

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

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

Открыть доступ

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

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях:

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

Изначально автомат находится в стартовом состоянии [math]s[/math] . Автомат считывает символы по очереди. При считывании очередного символа [math]p_i[/math] автомат переходит в состояние [math]\delta(q, p_i)[/math] , где [math]q[/math] — текущее состояние автомата. Процесс продолжается до тех пор, пока не будет достигнут конец входного слова.

Определение:

Будем говорить, что автомат допускает (англ. accept) слово, если после окончания описанного выше процесса автомат окажется в допускающем состоянии.

Замечание. Если в какой-то момент из текущего состояния нет перехода по считанному символу, то будем считать, что автомат не допускает данное слово. При реализации вместо отдельного рассмотрения данного случая иногда удобно вводить фиктивную нетерминальную «дьявольскую вершину» (также тупиковое состояние, сток), из которой любой переход ведет в неё же саму, и заменить все несуществующие переходы на переходы в «дьявольскую вершину».

Способы представления

Диаграмма переходов

Диаграмма переходов — граф, вершины которого соответствуют состояниям автомата, а рёбра — переходам между состояниями.

[math]\bigcirc[/math] — нетерминальное состояние, [math]\circledcirc[/math] — терминальное состояние, Стрелка [math]\downarrow[/math] указывает на начальное состояние.

Пример	Описание
	Автомат для поиска образца в тексте для строки [math]abbab[/math] .
	Автомат, принимающий непустые строки из чередующихся символов [math]a[/math] и [math]b[/math] ,без «дьявольской вершины».
	Автомат, принимающий непустые строки из чередующихся символов [math]a[/math] и [math]b[/math] , с «дьявольской вершиной».

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

Таблица переходов [math]T (|Q| \times |\Sigma|)[/math] , дающая табличное представление функции [math]\delta[/math] .

[math]M = (Q, \Sigma , \delta, q_0, F)[/math] , где

• [math]Q = [/math] ,
• [math]\Sigma = \[/math] ,
• [math]q_0 = S_1[/math] ,
• [math]F = [/math] ,
• [math]\delta[/math] — функция переходов, представленная таблицей:

[math]0[/math]	[math]1[/math]
[math]S_1[/math]	[math]S_2[/math]	[math]S_1[/math]
[math]S_2[/math]	[math]S_1[/math]	[math]S_2[/math]

Автоматные языки

Определение:

Мгновенное описание (конфигурация) (англ. snapshot) — пара [math]\langle q, \alpha \rangle[/math] , где [math]q[/math] — текущее состояние, [math]\alpha[/math] — оставшиеся символы.

Будем говорить, что конфигурация [math]\langle p, \beta \rangle[/math] выводима из [math]\langle q, \alpha \rangle[/math] за один шаг [math](\langle q, \alpha \rangle \vdash \langle p, \beta \rangle)[/math] , если:

• [math]\alpha = c\beta[/math] ,
• [math]\delta (q, c)=p [/math] .

Будем говорить, что конфигурация [math]\langle p, \beta \rangle[/math] выводима из [math]\langle q, \alpha \rangle[/math] за конечное число шагов [math](\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle)[/math] , если [math]\exists n:[/math]

• [math]\alpha = c_1 c_2 . c_n\beta[/math] ,
• [math]\langle q, c_1 c_2 c_3 . c_n\beta \rangle \vdash \langle u_1, c_2 c_3 . c_n\beta \rangle \vdash \langle u_2, c_3 . c_n\beta \rangle \vdash . \vdash \langle u_, c_n\beta \rangle \vdash \langle p, \beta \rangle[/math] .

[math]\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle[/math] .

Определение:

Множество [math]L(\mathcal)=\[/math] называется языком автомата (англ. automata’s language) [math]\mathcal[/math] .

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

Определение:

Множество языков всех ДКА образует множество автоматных языков [math]\mathrm[/math] .

Изоморфизм двух автоматов

Определение:

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

Задача:

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

Алгоритм

Из определения следует, что если автоматы изоморфны, то можно их состояния занумеровать одним способом так, что вершины из разных автоматов с одинаковыми номерами будут равны — то есть в каждом из этих двух состояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке обхода в глубину по символам в лексикографическом порядке и просто проверить состояния с одинаковыми номерами на равенство. Если все состояния будут равны, то автоматы будут равны, в нашем случае будет следовать изоморфизм двух автоматов. Асимптотика алгоритма совпадает с асимптотикой обхода в глубину, то есть [math]O(N + M) [/math] , где [math] N[/math] — суммарное число вершин в автоматах, [math] M[/math] — суммарное число ребер.

Псевдокод

• [math] \mathtt [/math] — множество пар [math]\langle a[/math] , [math]T \rangle[/math] , где [math] a \in \Sigma[/math] , [math]T \in Q[/math]
• [math] \mathtt [/math] — массив, где каждому состоянию первого автомата соответствует найденное состояние второго автомата.

boolean dfs(u: Vertex, v: Vertex): visited[u] = true // заметим, что достаточно только одного массива [math]\mathtt[/math] на два автомата if (v.terminal != u.terminal) return false associations[u] = v boolean result = true for ([math]\langle c, q \rangle[/math] : u.transitions) Vertex t1 = u.transitions.getVertex(c) Vertex t2 = v.transitions.getVertex(c) if одна из вершин t1, t2 дьявольская, а другая — нет return false if (visited[t1]) result = result and t2 == associations[t1] else result = result and dfs(t1, t2) return result

См. также

• Недетерминированные конечные автоматы
• Автомат Кнута-Морриса-Пратта
• Суффиксный автомат
• Алгоритм Ахо-Корасик
• Теорема Клини (совпадение классов автоматных и регулярных языков)

Источники информации

• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7.
• Wikipedia — Deterministic finite automaton

• Теория формальных языков
• Автоматы и регулярные языки