de Mark Shead

Înțelegerea mașinilor de stat

O introducere în conceptele de informatică

Informatica ne permite să programăm, dar este posibil să facem o mulțime de programare fără a înțelege conceptele de bază ale informaticii.

Nu este întotdeauna un lucru rău. Când programăm, lucrăm la un nivel mult mai ridicat de abstractizare.

Când conducem o mașină, ne preocupăm doar cu două sau trei pedale, un schimbător de viteze și un volan. Puteți opera în siguranță o mașină fără a avea o idee clară despre modul în care funcționează.

Cu toate acestea, dacă doriți să operați o mașină chiar în limitele capacităților sale, trebuie să știți mult mai multe despre automobile decât doar cele trei pedale, schimbătorul de viteze și volanul.

ad-banner

Același lucru este valabil și pentru programare. O mulțime de muncă de zi cu zi poate fi realizată cu o înțelegere redusă sau deloc a informaticii. Nu trebuie să înțelegeți teoria computației pentru a construi un formular „Contactați-ne” în PHP.

Cu toate acestea, dacă intenționați să scrieți cod care necesită un calcul serios, va trebui să înțelegeți mai multe despre modul în care funcționează calculul sub capotă.

Scopul acestui articol este de a oferi un fundal fundamental pentru calcul. Dacă există interes, s-ar putea să urmăresc câteva subiecte mai avansate, dar acum vreau să analizez logica din spatele unuia dintre cele mai simple dispozitive de calcul abstracte – un mașină cu stare finită.

Mașini cu stare finită

O mașină cu stare finită este o abstracție matematică utilizată pentru proiectarea algoritmilor.

În termeni mai simpli, o mașină de stare va citi o serie de intrări. Când citește o intrare, va trece la o stare diferită. Fiecare stare specifică la ce stare să treacă, pentru o intrare dată. Sună complicat, dar este într-adevăr destul de simplu.

Imaginați-vă un dispozitiv care citește o bucată lungă de hârtie. Pentru fiecare centimetru de hârtie este imprimată o singură literă – fie litera „a”, fie litera „b”.

0*xO3Fuvo1mL jczfC
O bandă de hârtie, cu opt litere imprimate pe ea

Pe măsură ce mașina de stat citește fiecare literă, aceasta schimbă starea. Iată o mașină de stare foarte simplă:

0*msRB3BVpVkGVgEOd

Cercurile sunt „stări”În care se află mașina. Săgețile sunt tranziții. Deci, dacă sunteți în stare s și citiți un „a”, veți trece la stare q. Dacă citiți un „b”, veți rămâne în stare s.

Deci, dacă începem s și citim banda de hârtie de mai sus de la stânga la dreapta, vom citi „a” și vom trece la stare q.

Apoi, vom citi „b” și vom trece înapoi la stare s.

Un alt „b” ne va ține aprins s, urmat de un „a” – care ne mută înapoi la q stat. Destul de simplu, dar ce rost are?

Ei bine, se dovedește că puteți rula o bandă prin mașina de stări și să spuneți ceva despre succesiunea literelor, examinând starea pe care ajungeți.

În mașina noastră de stare simplă de mai sus, dacă ajungem la stare s, banda trebuie să se termine cu litera „b”. Dacă ajungem în stare q, banda se termină cu litera „a”.

Acest lucru poate suna inutil, dar există un groaznic a problemelor care pot fi rezolvate cu acest tip de abordare. Un exemplu foarte simplu ar fi să stabilim dacă o pagină de HTML conține aceste etichete în această ordine:

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

Mașina de stări se poate muta într-o stare care arată că a citit eticheta html, se buclă până ajunge la eticheta de cap, se buclă până ajunge la eticheta de închidere a capului și așa mai departe.

Dacă ajunge cu succes la starea finală, atunci aveți acele etichete în ordinea corectă.

Mașinile cu stare finită pot fi, de asemenea, utilizate pentru a reprezenta multe alte sisteme – cum ar fi mecanica unui contor de parcare, a mașinii pop, a pompei automate de gaz și a tot felul de alte lucruri.

Mașini cu stări finite deterministe

Mașinile de stat la care ne-am uitat până acum sunt toate determinat mașini de stat. Din orice stat, există doar unu tranziție pentru orice intrare permisă. Cu alte cuvinte, nu pot exista două căi care să iasă dintr-o stare când citiți litera „a”. La început, acest lucru sună prostesc pentru a face chiar această distincție.

La ce bun un set de decizii dacă aceeași contribuție poate duce la trecerea la mai multe state? Nu poți spune unui computer, if x == true apoi executați doSomethingBig sau executați doSomethingSmall, poti tu?

Ei bine, poți cam cu o mașină de stat.

Ieșirea unei mașini de stare este starea sa finală. Trece prin toate procesările sale, apoi se citește starea finală și atunci se ia o acțiune. O mașină de stat nu do orice se deplasează de la stat la stat.

Procesează și, când ajunge la final, starea este citită și ceva extern declanșează acțiunea dorită (de exemplu, distribuirea unei cutii de sodă). Acesta este un concept important atunci când vine vorba de nedeterminist mașini cu stare finită.

Mașini de stat finit nedeterministe

Mașinile cu stări finite nedeterministe sunt mașini cu stări finite la care poate duce o intrare dată dintr-o anumită stare mai mult de un stare diferită.

De exemplu, să presupunem că vrem să construim o mașină cu stări finite care poate recunoaște șiruri de litere care:

  • Începeți cu litera „a”
  • și sunt apoi urmate de zero sau mai multe apariții ale literei „b”
  • sau, zero sau mai multe apariții ale literei „c”
  • sunt terminate de următoarea literă a alfabetului.

Șirurile valide ar fi:

  • abbbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac (zero apariții ale b)
  • anunț (zero apariții ale c)

Deci, va recunoaște litera „a” urmată de zero sau mai multe din aceeași literă „b” sau „c”, urmată de următoarea literă a alfabetului.

O modalitate foarte simplă de a reprezenta acest lucru este cu o mașină de stare care arată ca cea de mai jos, unde o stare finală de t înseamnă că șirul a fost acceptat și se potrivește cu modelul.

0*3QzqRMfRCh28
Model de potrivire a mașinii cu stări finite

Vedeți problema? Din punctul de plecare s, nu știm ce cale să luăm. Dacă citim litera „a”, nu știm dacă să mergem la stat q sau r.

Există câteva modalități de a rezolva această problemă. Unul este prin retrogradare. Pur și simplu luați toate căile posibile și ignorați sau ieșiți din cele în care vă blocați.

Acesta este practic modul în care funcționează majoritatea computerelor care joacă șah. Ei privesc toate posibilitățile – și toate posibilitățile acelor posibilități – și aleg calea care le oferă cel mai mare număr de avantaje față de adversarul lor.

Cealaltă opțiune este de a converti mașina nedeterministă într-o mașină deterministă.

Unul dintre atributele interesante ale unei mașini nedeterministe este că există un algoritm pentru a transforma orice mașină nedeterministă într-una deterministă. Cu toate acestea, este adesea mult mai complicat.

Din fericire pentru noi, exemplul de mai sus este doar puțin mai complicat. De fapt, acesta este suficient de simplu încât îl putem transforma într-o mașină deterministă în capul nostru, fără ajutorul unui algoritm formal.

Mașina de mai jos este o versiune deterministă a mașinii nedeterministe de mai sus. În mașina de mai jos, o stare finală de t sau v este atins de orice șir acceptat de mașină.

0*Sp eR3qz6X2w vPo
O mașină deterministică a stărilor finite

Modelul nedeterminist are patru stări și șase tranziții. Modelul determinist are șase stări, zece tranziții și două stări finale posibile.

Asta nu este mult mai mult, dar complexitatea crește de obicei exponențial. O mașină nedeterministă de dimensiuni moderate poate produce absolut imens mașinărie deterministă.

Expresii obisnuite

Dacă ați realizat orice tip de programare, probabil că ați întâlnit expresii regulate. Expresiile regulate și mașinile cu stare finită sunt funcțional echivalente. Orice lucru pe care îl puteți accepta sau potrivi cu o expresie regulată, poate fi acceptat sau asociat cu o mașină de stat.

De exemplu, modelul descris mai sus ar putea fi asortat cu expresia regulată: a(b*c|c*d)

Expresiile regulate și mașinile cu stări finite au, de asemenea, aceleași limitări. În special, ambele pot potrivi sau accepta doar modele care pot fi tratate cu memorie finită.

Deci, ce tip de tipare nu se pot potrivi? Să presupunem că doriți să potriviți doar șirurile „a” și „b”, unde există un număr de „a” urmat de un număr egal de „b”. Sau n ‘a este urmat de n ‘b’s, unde n este un număr.

Exemple ar fi:

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb

La început, aceasta pare o treabă ușoară pentru o mașină cu stare finită. Problema este că veți rămâne rapid fără stări sau va trebui să vă asumați un număr infinit de stări – moment în care nu mai este finit mașină de stat.

Să presupunem că creați o mașină cu stări finite care poate accepta până la 20 ‘a, urmată de 20’ b. Acest lucru funcționează bine, până când veți obține un șir de 21 ‘a urmat de 21’ b – moment în care va trebui să vă rescrieți mașina pentru a gestiona un șir mai lung.

Pentru orice șir pe care îl puteți recunoaște, există unul puțin mai lung pe care mașina dvs. nu îl poate recunoaște, deoarece nu mai are memorie.

Acest lucru este cunoscut sub numele de Pomparea Lemei care spune practic: „dacă modelul tău are o secțiune care poate fi repetată (ca cea) de mai sus, atunci modelul nu este regulat”.

Cu alte cuvinte, nu poate fi construită nici o expresie regulată, nici o mașină de stare finită care să recunoască toate șirurile care do se potrivesc cu modelul.

Dacă priviți cu atenție, veți observa că acest tip de model în care fiecare „a” are un „b” potrivit, arată foarte asemănător cu HTML. În orice pereche de etichete, este posibil să aveți orice număr de alte perechi de etichete potrivite.

Deci, în timp ce este posibil să utilizați o expresie regulată sau o mașină de stare finită pentru a recunoaște dacă o pagină de HTML are <html>, ead>; și elementele în ordinea corectă, nu puteți utiliza o expresie regulată pentru a afla dacă o pagină HTML întreagă este validă sau nu – deoarece HTML nu este un model obișnuit.

Mașini Turing

Deci, cum recunoști tipare neregulate?

Există un dispozitiv teoretic similar cu o mașină de stat, numită Mașină de Turing. Este similar cu o mașină cu stare finită prin aceea că are o bandă de hârtie pe care o citește. Dar, o mașină Turing poate șterge și scrie pe banda de hârtie.

Explicarea unei mașini Turing va ocupa mai mult spațiu pe care îl avem aici, dar există câteva puncte importante relevante pentru discuția noastră despre mașinile cu stări finite și expresiile regulate.

Mașinile Turing sunt computerizat complet – adică orice poate fi calculat, poate fi calculat pe o mașină Turing.

Deoarece o mașină Turing poate scrie și citi de pe banda de hârtie, nu se limitează la un număr finit de stări. Se poate presupune că banda de hârtie are o lungime infinită. Desigur, computerele reale nu au o cantitate infinită de memorie. Dar, de obicei, conțin suficientă memorie, astfel încât să nu atingeți limita pentru tipul de probleme pe care le procesează.

Turing Machines ne oferă un dispozitiv mecanic imaginar care ne permite să vizualizăm și să înțelegem cum funcționează procesul de calcul. Este deosebit de util în înțelegerea limitelor de calcul. Dacă există interes, voi face un alt articol despre Turing Machines în viitor.

De ce contează asta?

Deci, ce rost are? Cum vă va ajuta acest lucru să creați următorul formular PHP?

Indiferent de limitările lor, mașinile de stat sunt un concept central pentru calcul. În special, este semnificativ faptul că pentru orice mașină de stare nedeterministă pe care o puteți proiecta, există o mașină de stare deterministă care face același lucru.

Acesta este un punct cheie, deoarece înseamnă că vă puteți proiecta algoritmul în orice mod este cel mai ușor de gândit. După ce aveți un algoritm de lucru, îl puteți converti în orice formă este cea mai eficientă.

Înțelegerea faptului că mașinile cu stări finite și expresiile regulate sunt echivalente din punct de vedere funcțional deschide câteva utilizări incredibil de interesante pentru motoarele de expresie regulată – în special atunci când vine vorba de crearea regulilor de afaceri care pot fi schimbate fără a recompila un sistem.

O fundație în informatică vă permite să luați o problemă pe care nu știți cum să o rezolvați și să o raționați: „Nu știu cum să rezolv X, dar știu cum să rezolv Y. Și știu cum să convertiți o soluție pentru Y într-o soluție pentru X. Prin urmare, acum știu cum să rezolv X. ”

Dacă îți place acest articol, s-ar putea să te bucuri de mine Canalul canalului YouTube unde creez un videoclip ocazional sau un desen animat despre un aspect al creării de software. Am și eu un listă de email-uri pentru persoanele care ar dori un e-mail ocazional când produc ceva nou.

Publicat inițial la blog.markshead.com pe 11 februarie 2018.