Какого просветления я должен достичь после изучения конечных автоматов?

Я пересматривал Теорию вычислений для забавы, и этот вопрос меня мучил некоторое время (забавно, никогда не думал об этом, когда я изучал Теорию автоматов в моем старшекурснике). Итак, «почему» мы точно изучаем детерминированные и недетерминированные конечные автоматы (DFA / NFAs)? Итак, вот некоторые ответы, которые я придумал после ответа, но все еще не вижу их общего вклада в момент «ага»:

1. Изучить то, что они есть и не способны, т.е. ограничения
   • Почему?
2. Так как они являются базовыми моделями теоретических вычислений и заложат основу других более способных моделей вычислений.
   • Что делает их «основными»? Это то, что у них есть только один бит памяти и переходы между состояниями?
3. Хорошо, и что? Как все это способствует ответу на вопрос вычислимости? Кажется, машины Тьюринга помогают понять это очень хорошо, и есть «меньшие» модели вычислений, такие как PDA, DFA / NFAs / Regexes и т. Д. Но если кто-то не знает FA, на чем они упускают?

Так что, хотя я в некоторой степени «понимаю», я не могу ответить на этот вопрос для себя? Как лучше всего объяснить «зачем изучать D / N-FA»? На какой вопрос они хотят ответить? Как это помогает и почему это первое, чему учат в теории автоматов?

PS: я знаю о различных лексикографических приложениях и шаблонах, которые могут быть реализованы как таковые. Тем не менее, я не хочу знать, для чего он может быть использован практически, но какова была его причина для использования / изобретения / дизайна во время кульминации изучения теории вычислений. Исторически говоря, что побудило человека начать с этого и к какому «ага» пониманию оно должно привести? Если бы вам пришлось объяснить их важность студентам CS, только начинающим изучать теорию автоматов, как бы вы это сделали?

Я лично наслаждался несколькими Ага! моменты из изучения базовой теории автоматов. НФА и ДФА образуют микрокосм для теоретической информатики в целом.

1. Ведет ли недетерминизм к эффективности? Существуют стандартные примеры, когда минимальный детерминированный автомат для языка экспоненциально больше минимального недетерминированного автомата. Понимание этого различия для машин Тьюринга лежит в основе (теоретической) информатики. NFA и DFA предоставляют самый простой из известных мне примеров, где вы можете четко увидеть строгий разрыв между детерминизмом и недетерминизмом.
2. Вычислимость! = Сложность. NFA и DFA представляют обычные языки и эквивалентны в своих вычислениях. Они отличаются в том, как они вычисляют.
3. Машины уточняют языки. Это другой взгляд на то, что мы вычисляем и как мы вычисляем. Вы можете думать о вычислимых языках (и функциях) как об определении класса эквивалентности автоматов. Это фундаментальное изменение перспективы в TCS, где мы сосредотачиваемся не только на том, что, но как на вычислениях, и пытаемся выбрать правильное «как» при разработке алгоритма или понимаем пространство различных «как» при изучении классов сложности.
4. Значение канонического представления. DFA - типичный пример структуры данных, допускающей каноническое представление. Каждый регулярный язык имеет уникальный минимальный DFA. Это означает, что при минимальном DFA важные операции, такие как включение языка, дополнение и проверка принятия слова, становятся тривиальными. Разработка и использование канонических представлений - полезный прием при разработке алгоритмов.
5. Отсутствие канонических представлений. Не существует общепринятого канонического представления регулярных выражений или NFA. Таким образом, несмотря на вышеприведенный пункт, канонические представления не всегда существуют. Вы увидите этот момент во многих различных областях информатики. (например, логические формулы высказываний также не имеют канонических представлений, в то время как ROBDD имеют).
6. Стоимость канонического представления. Вы даже можете понять разницу между NFA и DFA как алгоритмическую теорему о том, что не нужно обедать . Если мы хотим проверить включение языка между NFA или дополнить его, вы можете определить и минимизировать его и продолжить с этого момента. Тем не менее, эта операция «сокращения» обходится дорого. Вы увидите примеры канонизации по цене в нескольких других областях информатики.
7. Бесконечный! = Неразрешимый. Распространенным заблуждением является то, что проблемы бесконечного характера неразрешимы. Обычные языки содержат бесконечно много строк, но имеют несколько разрешимых свойств. Теория регулярных языков показывает, что бесконечность сама по себе не является источником неразрешимости.
8. Держите бесконечность на ладони своего автомата. Вы можете рассматривать конечный автомат исключительно как структуру данных для представления бесконечных множеств. ROBDD - это структура данных для представления булевых функций, которую вы можете понимать как представление конечных множеств. Конечный автомат - это естественное, бесконечное расширение ROBDD.
9. Смиренный Процессор. В современном процессоре много чего, но вы можете понять это как конечный автомат. Именно эта реализация сделала компьютерную архитектуру и дизайн процессора гораздо менее пугающей для меня. Это также показывает, что на практике, если вы аккуратно структурируете и манипулируете своими состояниями, вы можете очень далеко продвинуться с помощью конечных автоматов.
10. Алгебраическая перспектива. Обычные языки образуют синтаксический моноид и могут изучаться с этой точки зрения. В более общем плане вы можете в последующих исследованиях также спросить, какова правильная алгебраическая структура, соответствующая некоторой вычислительной задаче.
11. Комбинаторная Перспектива. Конечный автомат - это помеченный граф. Проверка того, принято ли слово, сводится к поиску пути в помеченном графе. Алгоритмы автоматов равносильны преобразованиям графов. Понимание структуры автоматов для различных подсемей регулярных языков является активной областью исследований.
12. Алгебра-язык-комбинаторика любовного треугольника. Теорема Майхилла-Нерода позволяет вам начать с языка и создать автомат или синтаксический моноид. Математически мы получаем перевод между очень разными типами математических объектов. Полезно иметь в виду такие переводы и искать их в других областях информатики, а также переключаться между ними в зависимости от вашего приложения.
13. Математика - это язык больших картин. Регулярные языки могут быть охарактеризованы с помощью NFA (графы), регулярных выражений (формальная грамматика), машин Тьюринга только для чтения (машина), синтаксических моноидов (алгебра), алгебр Клини (алгебра), монадической логики второго порядка и т. Д. Более общие Феномен состоит в том, что важные, устойчивые концепции имеют много разных математических характеристик, каждая из которых вносит свой вклад в наше понимание идеи.
14. Леммы для рабочего математика. Лемма прокачки - отличный пример теоретического инструмента, который вы можете использовать для решения различных задач. Работа с леммами - это хорошая практика для того, чтобы пытаться опираться на существующие результаты.
15. Необходимо! = Достаточно. Теорема Майхилла-Нерода дает необходимые и достаточные условия регулярности языка. Лемма прокачки дает нам необходимые условия. Сравнение двух и использование их в разных ситуациях помогло мне понять разницу между необходимыми и достаточными условиями в математической практике. Я также узнал, что многоразовое необходимое и достаточное условие - это роскошь.
16. Перспектива языка программирования. Регулярные выражения - это простой и красивый пример языка программирования. В конкатенации у вас есть аналог последовательной композиции, а в Kleene star у вас есть аналог итерации. Определяя синтаксис и семантику регулярных выражений, вы делаете шаг в направлении теории языка программирования, наблюдая индуктивные определения и композиционную семантику.
17. Перспектива компилятора. Перевод из регулярного выражения в конечный автомат также является простым теоретическим компилятором. Вы можете увидеть разницу между синтаксическим анализом, генерацией промежуточного кода и оптимизацией компилятора из-за разницы в чтении регулярного выражения, генерации автомата и последующей минимизации / определении автомата.
18. Сила итерации. Видя, что вы можете сделать в конечном автомате с циклом и без него, вы сможете оценить силу итерации. Это может помочь понять различия между цепями и машинами или между классической логикой и логикой с фиксированной точкой.
19. Алгебра и коалгебра. Регулярные языки образуют синтаксический моноид, который является алгебраической структурой. Конечные автоматы образуют то, что на языке теории категорий называется коалгеброй. В случае детерминированного автомата мы можем легко перемещаться между алгебраическим и коалгебраическим представлением, но в случае NFA это не так просто.
20. Арифметическая перспектива. Существует глубокая связь между вычислениями и теорией чисел. Вы можете понять это как утверждение о силе теории чисел и / или универсальности вычислений. Вы обычно знаете, что конечные автоматы могут распознавать четное количество символов, и что они не могут считать достаточно, чтобы соответствовать круглым скобкам. Но на сколько они способны? Конечные автоматы могут решать арифметические формулы Пресбургера. Самая простая процедура принятия решений, которую я знаю для арифметики Пресбургера, сводит формулу к автомату. Это один проблеск, из которого вы можете перейти к 10-й проблеме Гильберта, и ее решение привело к обнаружению связи между диофантовыми уравнениями и машинами Тьюринга.
21. Логическая Перспектива. Вычисления могут быть поняты с чисто логической точки зрения. Конечные автоматы могут характеризоваться слабой, монадической логикой второго порядка над конечными словами. Это мой любимый, нетривиальный пример логической характеристики вычислительного устройства. Описательная теория сложности показывает, что многие классы сложности также имеют чисто логические характеристики.
22. Конечные автоматы прячутся в местах, которые вы никогда не представляли. (Подсказка к комментарию Мартина Бергера о связи с теорией кодирования) Нобелевская премия 2011 года по химии была присуждена за открытие квазикристаллов. Математика, стоящая за квазикристаллами, связана с апериодическими мозаиками. Одна конкретная апериодическая мозаика самолета называется мозаикой «Картуил», которая состоит из формы воздушного змея и галстука-бабочки. Вы можете кодировать эти формы в терминах 0 и 1, а затем изучать свойства этих последовательностей, которые кодируют последовательности шаблонов. Фактически, если вы отобразите от 0 до 01 и от 1 до 0 и повторно примените эту карту к цифре 0, вы получите 0, 01, 010, 01001 и т. Д. Обратите внимание, что длины этих строк соответствуют последовательности Фибоначчи. Произведенные таким образом слова называются словами Фибоначчи. Определенные последовательности форм, наблюдаемые в мозаиках Пенроуза, могут быть закодированы как слова Фибоначчи. Такие слова были изучены с точки зрения теоретико-автоматических вычислений, и угадайте, что некоторые семейства слов принимаются конечными автоматами, и даже предоставляют примеры поведения в худшем случае для стандартных алгоритмов, таких как алгоритм минимизации Хопкрофта. Пожалуйста, скажи мне, что у тебя кружится голова.

Я мог бы продолжать. (И дальше.) * Я считаю полезным иметь автоматы в затылке и время от времени вспоминать их, чтобы понять новую концепцию или получить представление о математических идеях высокого уровня. Я сомневаюсь, что обо всем, что я упомянул выше, можно рассказать в первых лекциях курса или даже в первом курсе. Это долгосрочные вознаграждения, основанные на первоначальных инвестициях в начальные лекции курса теории автоматов.

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

Есть много веских теоретических причин для изучения N / DFA. Два, которые сразу приходят на ум:

1. Машины Тьюринга (мы думаем) фиксируют все, что вычислимо. Однако мы можем спросить: какие части машины Тьюринга являются «существенными»? Что происходит, когда вы ограничиваете машину Тьюринга различными способами? DFAs - очень серьезное и естественное ограничение (устранение памяти). КПК являются менее серьезным ограничением и т. Д. Теоретически интересно посмотреть, что дает вам память и что происходит, когда вы обходитесь без нее. Это кажется мне очень естественным и основным вопросом.

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

Спрашивать, почему нужно изучать DFAs, все равно, что спрашивать, почему нужно изучать теорему Годеля о полноте, когда по-настоящему интересной является его теорема о неполноте .

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

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

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

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

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

Государственный. вам нужно понять, что можно моделировать мир (для определенных задач) как конечное пространство состояний, и в этих настройках можно подумать о вычислениях. Это простое понимание, но чрезвычайно полезно, если вы занимаетесь программированием - вы будете сталкиваться с состоянием снова и снова и снова, и FA даст вам возможность подумать о них. Я считаю это достаточным оправданием для преподавания полного класса. Конечно, состояние может быть детерминированным или недетерминированным. Таким образом DFA и NFA, но вы можете конвертировать между ними и т. Д.

Вторая вещь, которую нужно выучить, - это теорема Халтинга. Что связано с теоремой Гёделя о неполноте. (Вы не можете построить машину, которая может вычислить все, и есть математические утверждения, которые вы не можете ни доказать, ни опровергнуть, и поэтому их необходимо принимать за аксиомы. То есть мы живем в мире, который не имеет конечного описания или реального оракулы - ты для нас!)

Итак, я закончил обучение по математике, и вы привыкли к мысли, что вы изучаете вещи, которые вы не знаете, почему вы учитесь (теория групп, теория мер, теория множеств, гильбертовы пространства и т. Д., И т. Д., И т. Д. [Все хорошие вещи КСТАТИ]). Есть кое-что, что можно сказать об обучении тому, как учиться - в следующий раз вам придется выучить некоторую причудливую математику (потому что вы должны использовать это, чтобы сделать что-то там в реальном мире), что выглядит очень странно, если вы идете с ходу. В частности, третье, чему нужно научиться, - это математическая зрелость - умение тщательно спорить о вещах, знать, когда доказательства правильны или нет, записывать доказательства и т. Д. Если у вас это уже есть, этот курс прост, и вам будет все равно много почему вы изучаете это.

За исключением этого, курс - пустая трата вашего времени, как и все остальное. В частности, вы можете жить счастливой жизнью, не зная этого материала. Но это буквально верно для всех знаний. Более менее. Для меня курс в университете стоит своего времени, если вы посмотрите на мир по-другому после его изучения. Это определенно один из курсов, который изменил мой взгляд на мир. Что еще можно спросить?

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

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

Вы задаете (как минимум) два разных вопроса: (а) Какие части теории в настоящее время строятся на конечных автоматах? (б) Почему конечные автоматы были разработаны в первую очередь? Я думаю, что лучший способ справиться с последним - взглянуть на старые документы, такие как:

• Рабин, Скотт, Конечные автоматы и проблемы их решения , 1959

Вот первые два абзаца:

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

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

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

Другая причина в том, что это относительно практические теоретические модели. Машина Тьюринга, помимо невозможности бесконечной ленты, является своего рода неловким приспособлением для программирования компьютера (обратите внимание, что это не очень хорошая аналогия для начала!). КПК и DFA, однако, вполне поддаются модели реальных программ в том смысле, что дизайн PDA / DFA часто можно легко превратить в реальную программу. Например, дизайн компилятора широко использует их. Таким образом, в такого рода точках связи между теорией и практикой мы получаем представление о том, как все это связано друг с другом и что мы можем и не можем делать.

Проверьте игру «Живой бинарный сумматор» здесь: http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html Я использовал эту игру для моих учеников в первых главах о DFA / NFA. Это иллюстрирует две важные вещи в теории автоматов:

1. Как превратить психический процесс в простой механический
2. Что на самом деле означает абстракция. Два состояния, как C и Z выше, могут быть любыми: транзисторы в компьютере, гидравлический механизм или два человека!

Это иногда приносит момент «Ага» моим ученикам.

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

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

На самом деле, мои ученики иногда спрашивают именно об этом - потратив большую часть семестра на конечные автоматы и, наконец, прибыв на машины Тьюринга. Зачем тратить столько времени на более слабый формализм, если доступен более сильный? Поэтому я объясняю присущий компромисс между выразительной силой и аналитической сложностью. Более богатые модели, как правило, сложнее анализировать. Дихотомия DFA vs. TM является экстремальной, поскольку проблема членства тривиальна для одного и неисчислима для другого. Менее экстремальным примером будет DFA против PDA. Проблема принадлежности к последним оказывается эффективно разрешимой, но решение вовсе не тривиально. Мы наблюдаем это во многих областях математики и науки: изучите простую модель, чтобы получить как можно более полное понимание, которое обычно приводит к пониманию и более сложных моделей.

Я вижу несколько ответов, называющих FM «меньшими», чем машины Тьюринга.

Основное внимание в аспирантуре, которую я выбрал, заключалось в их эквивалентности, а не в различиях. Для каждой модели FSM, которую мы изучали, мы должны были доказать их эквивалентность машинам Тьюринга. Это делается путем внедрения машины Тьюринга в FSM. IIRC, мы также изучили некоторые другие компьютерные модели, которые не реализуют ТМ, но я забыл, что это были. Дело в том, что если вы можете реализовать TM, вы можете запустить любую программу TM на модели, учитывая достаточно большой аналог ленты для выполняемой задачи.

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

Это было мне интуитивно понятно, когда примерно в то же время (1984) я обнаружил язык FORTH. Его исполнительный движок построен на чистой реализации PDA Dual Stack. Идя глубже, я увлекаюсь этим же движком под компиляторами выражений.

Хотя для меня реальным влиянием FSM было открытие книги «Теория конечных автоматов» Трахтенброта и Корзинского (?), Когда мне было 18 лет, открытие, которое, по сути, дало мне мою карьеру.