Понимание государственных машин

ponimanie gosudarstvennyh mashin?v=1656679454

от Марка Шеда

Введение в понятие информатики

Информатика позволяет нам программировать, но можно многое программировать, не понимая основных концепций информатики.

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

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

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

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

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

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

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

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

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

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

0*xO3Fuvo1mL-jczfC
Бумажная лента, на которой опубликовано восемь букв

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

0*msRB3BVpVkGVgEOd

Круги — это «государства”, в котором может находиться машина. Стрелки – это переходы. Итак, если вы в гос с и прочитать «а», вы перейдете в состояние q. Если вы прочтете букву «б», вы останетесь в состоянии с.

Итак, если мы начнем дальше с и прочтите бумажную ленту выше слева направо, мы прочтем «а» и перейдем к состоянию q.

Затем мы прочтем «b» и вернемся к состоянию с.

Другая буква «б» удержит нас сза которым следует «a», что возвращает нас к q состояние. Достаточно просто, но какой смысл?

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

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

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

<html>   <head> </head>   <body> </body> </html>

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

Если он успешно достигает конечного состояния, то у вас есть эти конкретные метки в правильном порядке.

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

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

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

Какая польза от набора решений, если тот же вход может привести к переходу в несколько состояний? Вы не можете сказать компьютеру, if x == true затем выполните doSomethingBig или выполнить doSomethingSmallты можешь?

Ну, вы вроде бы можете с государственной машиной.

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

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

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

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

Например, скажем, мы хотим построить конечный автомат, который может распознавать строки букв, которые:

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

Допустимые строки будут:

  • аббббббббб
  • abbbc
  • accd
  • acccccd
  • ac (ноль вхождений b)
  • объявление (ноль случаев c)

Таким образом, он распознает букву «a», за которой следует ноль или больше тех же букв «b» или «c», а затем следующая буква алфавита.

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

0*3QzqRMfRCh28-xe1
Конечный автомат с совпадением шаблонов

Вы видите проблему? С начальной точки с, мы не знаем, какой путь выбрать. Если мы читаем букву «а», мы не знаем, идти ли в штат q или r.

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

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

Другим вариантом является превращение недетерминированной машины в детерминированную.

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

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

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

0*Sp_eR3qz6X2w-vPo
Детерминированный конечный автомат

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

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

Регулярные выражения

Если вы занимались каким-либо типом программирования, вы, вероятно, сталкивались с регулярными выражениями. Регулярные выражения и конечные автоматы функционально эквивалентны. Все, что вы можете принять или сопоставить с регулярным выражением, может быть принято или сопоставлено с конечным автоматом.

Например, описанный выше шаблон можно сопоставить с регулярным выражением: a(b*c|c*d)

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

Итак, с каким типом шаблонов они не совпадают? Допустим, вы хотите сопоставить только строки «a» и «b», где есть количество «a», за которыми следует равное количество «b». Или п «a» следует п ‘b’s, где п есть некоторое число.

Примеры:

  • о
  • aabb
  • ааааааббббб
  • аааааааааааааааааааааааааааааааааааааа

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

Предположим, что вы создаете конечный автомат, который может принимать до 20 ‘a’, а затем 20 ‘b’. Это работает отлично, пока вы не получите строку из 21 ‘a’, за которой следует 21 ‘b’ — после этого вам нужно будет переписать вашу машину для обработки более длинной строки.

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

Это известно как Лема о накачке который в основном говорит: «если ваш шаблон имеет раздел, который можно повторить (как тот) выше, шаблон не является обычным».

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

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

Итак, хотя вы можете использовать регулярное выражение или конечный автомат, чтобы распознать, имеет ли страница HTML <htмл>, ead>; и элементы в правильном порядке, вы не можете использовать регулярное выражение, чтобы определить, вся страница HTML действительна или нет, поскольку HTML не является регулярным шаблоном.

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

Как распознать нерегулярные узоры?

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

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

Машины Тьюринга есть вычислительно завершено – то есть все, что можно вычислить, можно вычислить на машине Тьюринга.

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

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

Почему это имеет значение?

Итак, какой смысл? Как это поможет создать следующую форму PHP?

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

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

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

База по информатике позволяет вам взять проблему, которую вы не знаете, как решить, и рассуждать: «Я не знаю, как решить X, но я знаю, как решить Y. И я знаю, как превратить решение для Y в решение для X. Итак, теперь я знаю, как решить X».

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

Впервые опубликовано на blog.markshead.com 11 февраля 2018 года.

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

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