С чем едят конечный автомат
Машина Тьюринга и машина состояний, детерминированный и недетерминированный конечный автомат, конечный автомат Мура и конечный автомат Мили. Голова кругом от всех этих понятий. Как во всем этом разобраться новичку? Тем более, что и у бывалых спецов бывает такая каша в голове из этих понятий. Чего только стоит вебинар от Яндекс Практикум на тему «Конечные автоматы в реальной жизни». Именно случайный просмотр этого вебинара сподвиг меня написать статью. Я обратил внимание, что даже более опытные лекторы ловко жонглируют всеми этими понятиями или подменяют одни другими в своих лекциях. С этим можно просто смириться, или дойти до безумия, разбираясь что к чему. И как со всем этим жить начинающему ардуинщику, если про конечные автоматы в программировании трубят из каждого утюга, а добраться до истины самостоятельно непросто?
Не гарантирую, что после прочтения статьи все сразу станет на свои места, но, как минимум, постараемся выудить из всей этой «каши» что-то полезное для себя. Так что усаживайтесь по удобнее, тема не простая, под катом будет много текста.
❯ Во всем виноваты математики
Да, именно так. Математика — это наука с долгой историей. Наука очень увлекательная, и поэтому она затягивает все большее количество умов. И каждому математику в душе хочется стать новым Пифагором, Евклидом, Лобачевским. А для этого необходимо постоянно расширять поле деятельности. Как только появляется какое-то новое научное направления, математики тут же жадно накидываются на него и изобретают свои новые теории.
Язык у математиков весьма своеобразный, совершенно непредназначенный для того, чтобы на нем разговаривать. Вот почему неподготовленному человеку в этих теориях сложно разобраться. К тому же, новые теории всегда строятся на уже имеющихся, происходит заимствование знакомых ранее понятий и адаптация их к новым условиям. От того путаницы становится все больше, остается ждать, пока все это как следует устоится.
Такая же участь ждала и электронику на заре ее развития. На ранних парах электроника была нераздельно связана со словом «радио» (радиоэлектроника), и ориентирована на радиосвязь. Новое прикладное применение обрела для себя тригонометрия, подтянулась теория сигналов, преобразования Фурье и еще много чего интересного.
❯ Комбинационные логические схемы
С развитием электроники от нее стали откалываться новые направления. Одно из таких — вычислительная техника. И тут математики тоже не остались в стороне. Хорошим подспорьем стала дискретная математика, от которой перешли к математической теории вычислительной техники.
К компьютерам вычислительная техника пришла далеко не сразу. Сперва появились комбинационные логические схемы. К таким схема можно отнести знакомые всем базовые логические вентили НЕ, И, ИЛИ, Исключающее ИЛИ и другие их комбинации. Шифраторы и дешифраторы можно считать более сложным вариантом комбинационных схем.
Особенность комбинационных схем заключается в том, что значение на выходе схемы зависит только от комбинации входных сигналов в текущий момент времени. Такие схемы не пригодны для сложных применений, так как не имеют элементов памяти. Описание работы комбинационных схем может быть выполнено в виде таблицы истинности или в виде логического выражения.
❯ Последовательностные логические схемы
Для реализации более сложных вычислений появились последовательностные логические схемы, значения на выходе которых зависят как от текущих входных значений, так и от предыдущих. Для этого последовательностные логические схемы содержат память. Эти схемы могут явно запоминать предыдущие значения определенных входов, или могут сжимать их в меньшее количество информации, называемое состоянием системы. Состояние системы содержит всю необходимую информацию о прошлом, необходимую для определения будущего поведения схемы.
В общем случае к последовательностным схемам можно отнести все схемы, которые не являются комбинационными. То есть последовательностные логические схемы — это те, значение выхода которых нельзя однозначно определить, зная лишь текущие значения входов.
Примером последовательностных логических схем могут служить защелки или различные типы триггеров. Они способны запоминать всего один бит информации. Объединение нескольких триггеров позволяет получить более сложные схемы параллельных, параллельно-последовательных, последовательно-параллельных и прочих регистров, которые способны хранить уже несколько бит.
❯ Конечный автомат Мура и Мили
Поведение некоторых последовательностных схем может быть весьма сложным, для описания их работы простые таблицы истинности уже не подходят. Чтобы упростить анализ сложных последовательностных логических схем, появилась теория цифровых автоматов для построения математических моделей, использующая понятие абстрактный автомат (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)- являются синонимами. Это связанно с особенностями терминологии на русском и английском языках.
Надеюсь, что дальнейшее изучение теории цифровых автоматов станет для вас значительно проще.
