Razumijevanje državnih strojeva

Uvod u koncepte informatike

Računarstvo nam omogućuje programiranje, ali moguće je puno programirati bez razumijevanja temeljnih koncepata informatike.

Ovo nije uvijek loše. Kada programiramo, radimo na mnogo višoj razini apstrakcije.

Kada vozimo automobil, brinemo se samo s dvije ili tri papučice, mjenjačem i volanom. Možete sigurno upravljati automobilom, a da nemate jasnu ideju kako to radi.

Međutim, ako želite upravljati automobilom na samim granicama njegovih mogućnosti, o automobilima morate znati puno više od samo tri papučice, mjenjača i upravljača.

Isto vrijedi i za programiranje. Mnogo svakodnevnog posla može se obaviti uz malo ili nimalo razumijevanja informatike. Ne morate razumjeti računsku teoriju da biste izgradili obrazac "Kontaktirajte nas" u PHP-u.

Međutim, ako planirate napisati kod koji zahtijeva ozbiljno računanje, morat ćete razumjeti malo više o tome kako izračunavanje funkcionira ispod haube.

Svrha ovog članka je pružiti neke temeljne pozadine za računanje. Ako postoji interes, možda ću se baviti nekim naprednijim temama, ali trenutno želim pogledati logiku jednog od najjednostavnijih apstraktnih računarskih uređaja - konačnog automata .

Konačni državni strojevi

Stroj s konačnim stanjima matematička je apstrakcija koja se koristi za dizajniranje algoritama.

Jednostavnije rečeno, državni stroj očitat će niz ulaza. Kad pročita ulaz, prebacit će se u drugo stanje. Svako stanje specificira u koje se stanje prebaciti za zadani ulaz. Ovo zvuči komplicirano, ali je zaista vrlo jednostavno.

Zamislite uređaj koji čita dugačak papir. Za svaki centimetar papira na njemu je otisnuto jedno slovo - ili slovo 'a' ili slovo 'b'.

Kako državni stroj čita svako slovo, mijenja stanje. Ovdje je vrlo jednostavan državni stroj:

Kružnice su " stanja " u kojima stroj može biti. Strelice su prijelazi . Dakle, ako ste u stanju s i pročitate 'a', prijeći ćete u stanje q . Ako pročitate "b", ostat ćete u stanju s .

Dakle, ako započnemo s i čitamo papirnatu vrpcu gore s lijeva na desno, pročitati ćemo 'a' i prijeći u stanje q .

Zatim ćemo pročitati 'b' i vratiti se u stanje s .

Još jedno 'b' zadržat će nas na s , nakon čega slijedi 'a' - što nas vraća natrag u stanje q . Dovoljno jednostavno, ali u čemu je poanta?

Pa, ispada da možete provući traku kroz državni stroj i reći nešto o slijedu slova, ispitujući stanje u kojem ste završili.

U našem jednostavnom državnom stroju gore, ako završimo u stanjima s , traka mora završiti slovom 'b'. Ako završimo u stanju q , vrpca završava slovom 'a'.

Ovo može zvučati besmisleno, ali postoji jako puno problema koji se mogu riješiti ovom vrstom pristupa. Vrlo jednostavan primjer bio bi utvrditi sadrži li stranica HTML-a ove oznake ovim redoslijedom:

Državni stroj može se premjestiti u stanje koje pokazuje da je pročitao html oznaku, petlju dok ne dođe do oznake glave, petlju dok ne dođe do oznake zatvaranja glave, i tako dalje.

Ako uspješno dođe do konačnog stanja, te određene oznake imate u ispravnom redoslijedu.

Strojevi s konačnim stanjima također se mogu koristiti za predstavljanje mnogih drugih sustava - kao što su mehanika mjerača parkirnih mjesta, automat za punjenje, automatizirana pumpa za gorivo i sve druge stvari.

Deterministički konačni strojevi

Državni strojevi koje smo do sada gledali su svi deterministički državni strojevi. Iz bilo kojeg stanja postoji samo jedan prijelaz za bilo koji dopušteni ulaz. Drugim riječima, ne mogu postojati dva puta koji vode iz stanja kada čitate slovo 'a'. U početku ovo zvuči glupo čak i da napravim tu razliku.

Kakva je korist od niza odluka ako isti unos može rezultirati prelaskom u više stanja? Ne možete reći računalu, if x == truepa izvršiti doSomethingBigili izvršiti doSomethingSmall, zar ne?

Pa, možete s državnim strojem.

Izlaz državnog stroja je njegovo konačno stanje. Prolazi kroz svu njegovu obradu, a zatim se očitava konačno stanje, a zatim se poduzima radnja. Državni stroj ne čini ništa dok se kreće od stanja do stanja.

Obrađuje, a kad dođe do kraja, stanje se očitava i nešto vanjsko pokreće željenu radnju (na primjer, točenje limenke od sode). Ovo je važan koncept kada su u pitanju nedeterministički strojevi s konačnim stanjima.

Nedeterministički strojevi konačnih stanja

Nedeterministički strojevi s konačnim stanjima su strojevi s konačnim stanjima kod kojih dani unos iz određenog stanja može dovesti do više različitih stanja.

Na primjer, recimo da želimo izgraditi konačni stroj koji može prepoznati nizove slova koja:

  • Počnite slovom 'a'
  • a zatim slijede nula ili više pojavljivanja slova 'b'
  • ili nula ili više pojavljivanja slova 'c'
  • završavaju se sljedećim slovom abecede.

Važeći nizovi bili bi:

  • abbbbbbbbbc
  • abbbc
  • prema
  • prema
  • ac (nula pojava b)
  • ad (nula pojavljivanja c)

Tako će prepoznati slovo 'a' nakon čega slijedi nula ili više istog slova 'b' ili 'c', nakon čega slijedi sljedeće slovo abecede.

Vrlo jednostavan način da se to predstavi je pomoću automata stanja koji izgleda poput donjeg, gdje konačno stanje t znači da je niz prihvaćen i odgovara uzorku.

Vidite li problem? Od polazne točke S , ne znamo kojim putem krenuti. Ako čitamo slovo 'a', ne znamo trebamo li ići u stanje q ili r.

Postoji nekoliko načina za rješavanje ovog problema. Jedno je vraćanje unatrag. Jednostavno idete svim mogućim stazama, a ignorirate ili se povlačite iz onih na kojima zapnete.

U osnovi tako funkcionira većina računala za igranje šaha. Oni promatraju sve mogućnosti - i sve mogućnosti tih mogućnosti - i odabiru put koji im daje najveći broj prednosti u odnosu na protivnika.

Druga je mogućnost pretvoriti nedeterministički stroj u deterministički stroj.

Jedan od zanimljivih atributa nedeterminističkog stroja je taj što postoji algoritam za pretvaranje bilo kojeg nedeterminističkog stroja u deterministički. Međutim, često je puno složenije.

Na našu sreću, gornji je primjer tek malo složeniji. Zapravo, ovaj je dovoljno jednostavan da ga možemo transformirati u deterministički stroj u svojoj glavi, bez pomoći formalnog algoritma.

Stroj u nastavku je deterministička verzija nedeterminističkog stroja gore. U donjem stroju konačno stanje t ili v postiže se bilo kojim nizom koji stroj prihvati.

Nedeterministički model ima četiri stanja i šest prijelaza. Deterministički model ima šest stanja, deset prijelaza i dva moguća konačna stanja.

To nije toliko puno više, ali složenost obično raste eksponencijalno. Neodređeni stroj umjerene veličine može proizvesti apsolutno ogroman deterministički stroj.

Regularni izrazi

Ako ste radili bilo koju vrstu programiranja, vjerojatno ste se susreli s regularnim izrazima. Regularni izrazi i automati konačnog stanja funkcionalno su ekvivalentni. Sve što možete prihvatiti ili upariti s regularnim izrazom, može se prihvatiti ili uporediti s državnim strojem.

Na primjer, gore opisani obrazac mogao bi se podudarati s regularnim izrazom: a(b*c|c*d)

Regularni izrazi i automati konačnog stanja također imaju ista ograničenja. Konkretno, oboje se mogu podudarati ili prihvaćati samo obrasce kojima se može rukovati s ograničenom memorijom.

Dakle, koji se obrasci ne mogu podudarati? Recimo da želite podudarati samo nizove 'a' i 'b', gdje postoji niz 'a' nakon kojih slijedi jednak broj 'b'. Ili n 'a slijede n ' b, gdje je n neki broj.

Primjeri bi bili:

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

U početku ovo izgleda kao lak posao za stroj s konačnim stanjima. Problem je u tome što ćete brzo ostati bez stanja ili ćete morati pretpostaviti beskonačan broj stanja - u tom trenutku to više nije konačni stroj.

Recimo da stvorite konačni automat koji može prihvatiti do 20 'a, a zatim 20' b. To funkcionira u redu, sve dok ne dobijete niz od 21 'a iza kojeg slijede 21' b - u tom ćete trenutku morati prepisati svoj stroj kako bi obradio duži niz.

Za bilo koji niz koji možete prepoznati postoji malo duži koji vaš stroj ne može prepoznati jer mu ponestaje memorije.

Ovo je poznato kao Pumping Lemma koja u osnovi kaže: "ako vaš uzorak ima odjeljak koji se može ponoviti (poput gornjeg), uzorak nije redovit".

Drugim riječima, ne može se konstruirati niti regularni izraz niti krajnji stroj koji će prepoznati sve nizove koji se podudaraju s uzorkom.

Ako pažljivo pogledate, primijetit ćete da ova vrsta uzorka gdje svaki 'a' ima podudaranje 'b', izgleda vrlo slično HTML-u. Unutar bilo kojeg para oznaka možete imati bilo koji broj drugih odgovarajućih parova oznaka.

Dakle, iako ćete možda moći upotrijebiti regularni izraz ili stroj krajnjeg stanja da biste prepoznali ima li stranica HTML-a ; i elemente u ispravnom redoslijedu, ne možete upotrijebiti regularni izraz da biste utvrdili je li cijela HTML stranica valjana ili ne - jer HTML nije redoviti obrazac. ml >, ead>

Turingovi strojevi

Pa kako prepoznati nepravilne obrasce ?

Postoji teoretski uređaj koji je sličan državnom stroju, nazvan Turingov stroj. Sličan je stroju s konačnim stanjima po tome što ima papirnatu traku koju čita. Ali, Turingov stroj može izbrisati i upisati na papirnatu traku.

Objašnjenje Turingova stroja zauzet će više mjesta koje imamo ovdje, ali postoji nekoliko važnih točaka važnih za našu raspravu o konačnim strojevima i regularnim izrazima.

Turingovi strojevi računski su cjeloviti - što znači sve što se može izračunati, može se izračunati na Turingovom stroju.

Budući da Turingov stroj može pisati kao i čitati s papirnate vrpce, nije ograničen na konačan broj stanja. Može se pretpostaviti da je papirna traka beskonačne duljine. Naravno, stvarna računala nemaju beskonačnu količinu memorije. No, obično sadrže dovoljno memorije, tako da ne dosegnete ograničenje za vrstu problema koje obrađuju.

Turingovi strojevi daju nam zamišljeni mehanički uređaj koji nam omogućava vizualizirati i razumjeti kako funkcionira računski proces. To je posebno korisno u razumijevanju granica računanja. Ako bude interesa, u budućnosti ću napraviti još jedan članak o Turingovim strojevima.

Zašto je ovo važno?

Pa, u čemu je poanta? Kako će vam ovo pomoći da stvorite sljedeći PHP obrazac?

Bez obzira na njihova ograničenja, državni strojevi vrlo su središnji koncept računanja. Konkretno, značajno je da za bilo koji nedeterministički državni stroj koji možete dizajnirati postoji deterministički državni stroj koji radi istu stvar.

Ovo je ključna stvar, jer znači da svoj algoritam možete dizajnirati na onaj način na koji je najlakše razmišljati. Nakon što stvorite ispravni algoritam, možete ga pretvoriti u bilo koji oblik koji je najučinkovitiji.

Razumijevanje da su automati konačnih stanja i regularni izrazi funkcionalno ekvivalentni otvara neke nevjerojatno zanimljive namjene za mehanizme regularnih izraza - posebno kada je u pitanju stvaranje poslovnih pravila koja se mogu mijenjati bez ponovnog sastavljanja sustava.

Temelj u računalnim znanostima omogućuje vam rješavanje problema koji ne znate riješiti i obrazložiti: „Ne znam riješiti X, ali znam Y. I znam kako pretvoriti rješenje za Y u rješenje za X. Stoga sada znam kako riješiti X. "

Ako vam se sviđa ovaj članak, možda ćete uživati ​​u mom YouTube kanalu na kojem stvorim povremeni videozapis ili crtić o nekom aspektu stvaranja softvera. Također imam mailing listu za ljude koji bi željeli prigodnu e-poštu kad proizvedem nešto novo.

Izvorno objavljeno na blog.markshead.com 11. veljače 2018.