Разбиране на държавни машини

Въведение в концепциите за компютърни науки

Компютърните науки ни дават възможност да програмираме, но е възможно да правим много програмиране, без да разбираме основните концепции на компютърните науки.

Това не винаги е лошо нещо. Когато програмираме, ние работим на много по-високо ниво на абстракция.

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

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

Същото важи и за програмирането. Много ежедневна работа може да бъде изпълнена с малко или никакво разбиране на компютърните науки. Не е нужно да разбирате изчислителна теория, за да създадете формуляр „Свържете се с нас“ в PHP.

Ако обаче планирате да напишете код, който изисква сериозни изчисления, ще трябва да разберете малко повече за това как работи изчислението под капака.

Целта на тази статия е да предостави някои основни условия за изчисленията. Ако има интерес, може да продължа с някои по-напреднали теми, но в момента искам да разгледам логиката зад едно от най-простите абстрактни изчислителни устройства - машина на крайно състояние .

Крайни държавни машини

Машината с крайно състояние е математическа абстракция, използвана за проектиране на алгоритми.

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

Представете си устройство, което чете дълъг лист хартия. За всеки инч хартия има отпечатана единична буква - или буквата „а“, или буквата „б“.

Докато държавната машина чете всяка буква, тя променя състоянието. Ето една много проста държавна машина:

Кръговете са „ състояния “, в които машината може да бъде. Стрелките са преходите . Така че, ако сте в състояние s и прочетете 'a', ще преминете към състояние q . Ако прочетете „b“, ще останете в състояние s .

Така че, ако започнем от s и прочетем хартиената лента отгоре отляво надясно, ще прочетем буквата „a“ и ще преминем към състояние q .

След това ще прочетем „b“ и ще се върнем към състоянието s .

Друго „b“ ще ни държи на s , последвано от „a“ - което ни връща обратно в състоянието q . Достатъчно просто, но какъв е смисълът?

Е, оказва се, че можете да прокарате лента през държавната машина и да разкажете нещо за последователността на буквите, като изследвате състоянието, в което се озовавате.

В нашия прост автомат по-горе, ако завършим в състояние s , лентата трябва да завършва с буква „b“. Ако завършим в състояние q , лентата завършва с буквата „a“.

Това може да звучи безсмислено, но има страшно много проблеми, които могат да бъдат решени с този тип подход. Много прост пример би бил да се определи дали една страница в HTML съдържа следните тагове в този ред:

Машината на състоянието може да се премести в състояние, което показва, че е прочело html маркера, цикъл, докато стигне до маркера head, цикъл, докато стигне до маркера за затваряне на главата и т.н.

Ако успее да стигне до крайното състояние, тогава тези конкретни маркери са в правилния ред.

Машините с крайно състояние също могат да бъдат използвани за представяне на много други системи - като механиката на паркинг метър, поп машина, автоматизирана газова помпа и всякакви други неща.

Детерминистични машини с крайно състояние

Държавните машини, които разгледахме досега, са всички детерминирани автомати на състоянието. От всяко състояние има само един преход за всеки разрешен вход. С други думи, не може да има два пътя, водещи от състояние, когато четете буквата „а“. Отначало това звучи глупаво дори да се прави това разграничение.

Каква полза от набор от решения, ако един и същ вход може да доведе до преминаване в повече от едно състояние? Не можеш да кажеш на компютър, if x == trueслед това да изпълниш doSomethingBigили изпълниш doSomethingSmall, нали?

Е, можеш с държавна машина.

Изходът на автомат на състоянието е крайното му състояние. Той преминава през цялата си обработка, след което се прочита окончателното състояние и след това се предприема действие. Държавна машина не прави нищо, докато се премества от състояние в състояние.

Той обработва и когато стигне до края, състоянието се чете и нещо външно задейства желаното действие (например, дозиране на сода). Това е важна концепция, когато става дума за не-детерминирани крайни автомати.

Недетерминирани машини с крайно състояние

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

Например, да кажем, че искаме да изградим машина с краен автомат, която може да разпознава низове от букви, които:

  • Започнете с буквата "а"
  • и след това са последвани от нула или повече повторения на буквата „b“
  • или, нула или повече повторения на буквата „c“
  • се прекратяват със следващата буква от азбуката.

Валидни низове ще бъдат:

  • abbbbbbbbbc
  • abbbc
  • съгл
  • в съответствие с
  • ac (нула на b)
  • ad (нула поява на c)

Така че ще разпознае буквата „а“, последвана от нула или повече от същата буква на „б“ или „в“, последвана от следващата буква от азбуката.

Много лесен начин да се представи това е с автомат на състояния, който прилича на този по-долу, където крайното състояние на t означава, че низът е приет и съответства на модела.

Виждате ли проблема? От отправна точка е , че не знаем кой път да поеме. Ако четем буквата „а“, не знаем дали да отидем в състоянието q или r.

Има няколко начина за решаване на този проблем. Единият е чрез връщане назад. Просто поемате по всички възможни пътища и игнорирате или се отдръпвате от онези, където сте заседнали.

По принцип така работят повечето компютри за игра на шах. Те разглеждат всички възможности - и всички възможности на тези възможности - и избират пътя, който им дава най-голям брой предимства пред опонента си.

Другият вариант е да превърнете недетерминираната машина в детерминирана машина.

Един от интересните атрибути на недетерминирана машина е, че съществува алгоритъм за превръщане на всяка недетерминирана машина в детерминирана. Често обаче е много по-сложно.

За наше щастие горният пример е само малко по-сложен. Всъщност този е достатъчно прост, за да можем да го превърнем в детерминирана машина в главата си, без помощта на официален алгоритъм.

Машината по-долу е детерминирана версия на недетерминираната машина по-горе. В машината отдолу крайното състояние на t или v се достига от всеки низ, който е приет от машината.

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

Това не е чак толкова повече, но сложността обикновено нараства експоненциално. Една средно голяма недетерминирана машина може да произведе абсолютно огромна детерминирана машина.

Редовни изрази

Ако сте правили някакъв тип програмиране, вероятно сте срещали регулярни изрази. Регулярните изрази и крайните автомати са функционално еквивалентни. Всичко, което можете да приемете или съчетаете с регулярен израз, може да бъде прието или съчетано с държавна машина.

Например, описаният по-горе шаблон може да бъде съчетан с регулярния израз: a(b*c|c*d)

Регулярните изрази и крайните автомати също имат същите ограничения. По-специално, и двамата могат да съвпадат или да приемат само модели, които могат да се обработват с крайна памет.

И така, какъв тип модели не могат да съвпадат? Да приемем, че искате да съвпадате само с низове от „a“ и „b“, където има няколко „a“, последвани от равен брой „b“. Или n 'a, последвани от n ' b, където n е някакво число.

Примери за това са:

  • аб
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbb

Отначало това изглежда като лесна работа за машина с краен режим. Проблемът е, че бързо ще останете без състояния, или ще трябва да приемете безкраен брой състояния - в този момент това вече не е машина с краен щат.

Да предположим, че създавате машина с краен автомат, която може да приема до 20 'a, последвани от 20' b. Това работи добре, докато не получите низ от 21 'a, последван от 21' b - в този момент ще трябва да пренапишете машината си, за да обработва по-дълъг низ.

За всеки низ, който можете да разпознаете, има един малко по-дълъг, който машината ви не може да разпознае, защото свършва паметта.

Това е известно като изпомпваща лема, която основно казва: „ако вашият модел има раздел, който може да се повтори (като този) по-горе, тогава моделът не е редовен“.

С други думи, не може да бъде конструиран нито регулярен израз, нито машина с крайно състояние, които да разпознават всички низове, които съвпадат с модела.

Ако погледнете внимателно, ще забележите, че този тип шаблон, при който всяко 'a' има съвпадащо 'b', изглежда много подобно на HTML. Във всяка двойка маркери може да имате произволен брой други съвпадащи двойки маркери.

Така че, макар че може да сте в състояние да използвате регулярен израз или машина с крайно състояние, за да разпознаете дали страница на HTML има ; и елементи в правилния ред, не можете да използвате регулярен израз, за ​​да разберете дали цялата HTML страница е валидна или не - защото HTML не е редовен модел.ml>, ead>

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

И така, как да разпознаете нередовните модели ?

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

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

Машините на Тюринг са изчислително пълни - което означава всичко, което може да бъде изчислено, може да бъде изчислено на машина на Тюринг.

Тъй като машина на Тюринг може да пише, както и да чете от хартиената лента, тя не се ограничава до ограничен брой състояния. Може да се приеме, че хартиената лента е безкрайна по дължина. Разбира се, истинските компютри нямат безкрайно количество памет. Но те обикновено съдържат достатъчно памет, така че да не достигнете лимита за типа проблеми, които обработват.

Turing Machines ни дават въображаемо механично устройство, което ни позволява да визуализираме и разберем как работи изчислителният процес. Това е особено полезно за разбиране на границите на изчисленията. Ако има интерес, ще направя друга статия за машините на Тюринг в бъдеще.

Защо това има значение?

И така, какъв е смисълът? Как това ще ви помогне да създадете следващия PHP формуляр?

Независимо от техните ограничения, държавните машини са много централно понятие за изчисленията. По-специално, важно е, че за всеки недетерминиран автомат на състоянието, който можете да проектирате, съществува детерминиран автомат на състоянието, който прави същото.

Това е ключов момент, защото това означава, че можете да проектирате своя алгоритъм по кой начин е най-лесно да се мисли. След като имате работещ алгоритъм, можете да го преобразувате във всякаква форма, която е най-ефективна.

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

Фондация в компютърните науки ви позволява да вземете проблем, който не знаете как да решите и да разсъждавате: „Не знам как да реша X, но знам как да реша Y. И знам как да конвертирам решение за Y в решение за X. Следователно сега знам как да реша X. "

Ако тази статия ви харесва, може да се насладите на моя канал в YouTube, където създавам случайно видео или карикатура за някакъв аспект от създаването на софтуер. Имам и пощенски списък за хора, които биха искали случайни имейли, когато създавам нещо ново.

Първоначално публикувано на blog.markshead.com на 11 февруари 2018 г.