Forståelse af statsmaskiner

En introduktion til datalogikoncepter

Datalogi giver os mulighed for at programmere, men det er muligt at lave en masse programmering uden at forstå de underliggende datalogiske begreber.

Dette er ikke altid en dårlig ting. Når vi programmerer, arbejder vi på et meget højere abstraktionsniveau.

Når vi kører bil, beskæftiger vi os kun med to eller tre pedaler, en gearskifte og et rat. Du kan betjene en bil sikkert uden at have nogen klar idé om, hvordan den fungerer.

Men hvis du vil betjene en bil ved de meget begrænsede muligheder, skal du vide meget mere om biler end bare de tre pedaler, gearskifte og rat.

Det samme gælder programmering. En masse hverdagsarbejde kan udføres med ringe eller ingen forståelse for datalogi. Du behøver ikke at forstå beregningsteori for at oprette en "Kontakt os" form i PHP.

Men hvis du planlægger at skrive kode, der kræver seriøs beregning, skal du forstå lidt mere om, hvordan beregning fungerer under emhætten.

Formålet med denne artikel er at give en grundlæggende baggrund for beregning. Hvis der er interesse, kan jeg følge op med nogle mere avancerede emner, men lige nu vil jeg se på logikken bag en af ​​de enkleste abstrakte beregningsenheder - en finite state machine .

Endelige tilstandsmaskiner

En finite state machine er en matematisk abstraktion, der bruges til at designe algoritmer.

I enklere termer vil en tilstandsmaskine læse en række input. Når den læser et input, skifter det til en anden tilstand. Hver tilstand specificerer, hvilken tilstand der skal skiftes til, for en given input. Dette lyder kompliceret, men det er virkelig ret simpelt.

Forestil dig en enhed, der læser et langt stykke papir. For hver tomme papir er der et enkelt bogstav trykt på det - enten bogstavet 'a' eller bogstavet 'b'.

Når statsmaskinen læser hvert bogstav, skifter det tilstand. Her er en meget enkel tilstandsmaskine:

Cirklerne er " stater ", som maskinen kan være i. Pilene er overgange . Så hvis du er i tilstand s og læser et 'a', overgår du til tilstand q . Hvis du læser et 'b', forbliver du i tilstand s .

Så hvis vi starter på s og læser papirbåndet over fra venstre mod højre, læser vi 'a' og flytter til tilstand q .

Derefter læser vi 'b' og flytter tilbage til tilstand s .

Et andet 'b' holder os på s , efterfulgt af et 'a' - som flytter os tilbage til q- tilstanden. Enkelt nok, men hvad er pointen?

Nå viser det sig, at du kan køre et bånd gennem statsmaskinen og fortælle noget om rækkefølgen af ​​bogstaver ved at undersøge den tilstand, du ender på.

I vores simple tilstandsmaskine ovenfor, hvis vi ender i tilstand s , skal båndet ende med bogstavet 'b'. Hvis vi ender i tilstand q , slutter båndet med bogstavet 'a'.

Dette lyder måske meningsløst, men der er en hel del problemer, der kan løses med denne type tilgang. Et meget simpelt eksempel ville være at afgøre, om en side med HTML indeholder disse tags i denne rækkefølge:

Statsmaskinen kan flytte til en tilstand, der viser, at den har læst html-koden, løkke, indtil den kommer til hovedkoden, løkke, indtil den kommer til koden til lukning af hoved osv.

Hvis det med succes når det til den endelige tilstand, har du de bestemte tags i den rigtige rækkefølge.

Finite state-maskiner kan også bruges til at repræsentere mange andre systemer - såsom mekanikken i en parkeringsmåler, popmaskine, automatiseret gaspumpe og alle mulige andre ting.

Deterministiske endelige maskiner

De statsmaskiner, vi har set på hidtil, er alle deterministiske statsmaskiner. Fra enhver tilstand er der kun en overgang for ethvert tilladt input. Med andre ord kan der ikke være to stier, der fører ud af en tilstand, når du læser bogstavet 'a'. Først lyder dette fjollet for selv at skelne.

Hvad gavner et sæt beslutninger, hvis det samme input kan resultere i at flytte til mere end en stat? Du kan ikke fortælle en computer, if x == trueså udfør doSomethingBigeller udfør doSomethingSmall, kan du?

Nå, du kan slags med en statsmaskine.

Outputtet fra en statsmaskine er dens endelige tilstand. Den gennemgår al sin behandling, og derefter læses den endelige tilstand, og derefter udføres en handling. En tilstand maskinen ikke gøre noget som den bevæger sig fra stat til stat.

Det behandles, og når det kommer til slutningen, læses tilstanden, og noget eksternt udløser den ønskede handling (for eksempel udlevering af en sodavand). Dette er et vigtigt begreb, når det kommer til ikke-deterministiske endelige statsmaskiner.

Ikke-deterministiske endelige statsmaskiner

Ikke-deterministiske finite state-maskiner er finite state-maskiner, hvor et givet input fra en bestemt tilstand kan føre til mere end en anden tilstand.

Lad os for eksempel sige, at vi vil bygge en finite state machine, der kan genkende strenge af bogstaver, der:

  • Start med bogstavet 'a'
  • og efterfølges af nul eller flere forekomster af bogstavet 'b'
  • eller, nul eller flere forekomster af bogstavet 'c'
  • afsluttes med det næste bogstav i alfabetet.

Gyldige strenge ville være:

  • abbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac (nul forekomster af b)
  • annonce (nul forekomster af c)

Så det genkender bogstavet 'a' efterfulgt af nul eller flere af samme bogstav 'b' eller 'c' efterfulgt af det næste bogstav i alfabetet.

En meget enkel måde at repræsentere dette på er med en tilstandsmaskine, der ligner den nedenfor, hvor en endelig tilstand af t betyder, at strengen blev accepteret og matcher mønsteret.

Ser du problemet? Fra startpunktet s ved vi ikke, hvilken vej vi skal tage. Hvis vi læser bogstavet 'a', ved vi ikke, om vi skal gå til staten q eller r.

Der er et par måder at løse dette problem på. Den ene er ved backtracking. Du tager simpelthen alle de mulige stier og ignorerer eller går ud af dem, hvor du sidder fast.

Sådan fungerer de fleste skakspilende computere. De ser på alle mulighederne - og alle mulighederne i disse muligheder - og vælger den vej, der giver dem størst antal fordele i forhold til deres modstander.

Den anden mulighed er at konvertere den ikke-deterministiske maskine til en deterministisk maskine.

En af de interessante egenskaber ved en ikke-deterministisk maskine er, at der findes en algoritme til at gøre enhver ikke-deterministisk maskine til en deterministisk. Det er dog ofte meget mere kompliceret.

Heldigvis for os er eksemplet ovenfor kun lidt mere kompliceret. Faktisk er denne enkel nok til at vi kan omdanne den til en deterministisk maskine i vores hoved uden hjælp fra en formel algoritme.

Maskinen nedenfor er en deterministisk version af den ikke-deterministiske maskine ovenfor. I nedenstående maskine opnås en endelig tilstand af t eller v af enhver streng, der accepteres af maskinen.

Den ikke-deterministiske model har fire tilstande og seks overgange. Den deterministiske model har seks tilstande, ti overgange og to mulige endelige tilstande.

Det er ikke så meget mere, men kompleksiteten vokser normalt eksponentielt. En ikke-deterministisk maskine i moderat størrelse kan producere en absolut enorm deterministisk maskine.

Regulære udtryk

Hvis du har foretaget nogen form for programmering, har du sandsynligvis stødt på regelmæssige udtryk. Regulære udtryk og finite state-maskiner er funktionelt ækvivalente. Alt, hvad du kan acceptere eller matche med et regulært udtryk, kan accepteres eller matches med en statsmaskine.

For eksempel kan det ovenfor beskrevne mønster matches med det regulære udtryk: a(b*c|c*d)

Regulære udtryk og finite state-maskiner har også de samme begrænsninger. Især kan de begge kun matche eller acceptere mønstre, der kan håndteres med begrænset hukommelse.

Så hvilken type mønstre kan de ikke matche? Lad os sige, at du kun vil matche strengene med 'a' og 'b', hvor der er et antal 'a'er efterfulgt af et lige stort antal' b'er. Eller n 'a efterfulgt af n ' b, hvor n er et tal.

Eksempler kan være:

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

Først ser det ud som et let job for en endelig statsmaskine. Problemet er, at du hurtigt løber tør for stater, eller du bliver nødt til at antage et uendeligt antal stater - på hvilket tidspunkt det ikke længere er en endelig statsmaskine.

Lad os sige, at du opretter en endelig tilstandsmaskine, der kan acceptere op til 20 'a efterfulgt af 20' b. Det fungerer fint, indtil du får en streng på 21 'a efterfulgt af 21' b - på hvilket tidspunkt skal du omskrive din maskine for at håndtere en længere streng.

For enhver streng, du kan genkende, er der en lidt længere, som din maskine ikke kan genkende, fordi den løber tør for hukommelse.

Dette er kendt som Pumping Lemma, der grundlæggende siger: "hvis dit mønster har et afsnit, der kan gentages (som det ovenfor), så er mønsteret ikke regelmæssigt".

Med andre ord kan hverken et regulært udtryk eller en endelig tilstandsmaskine konstrueres, der genkender alle strengene, der matcher mønsteret.

Hvis du ser nøje, vil du bemærke, at denne type mønster, hvor hver 'a' har en matchende 'b', ligner meget HTML. Inden for ethvert par tags kan du have et vilkårligt antal andre matchende tags.

Så selvom du muligvis kan bruge et regulært udtryk eller en endelig tilstandsmaskine til at genkende, om en side med HTML har ; og elementer i den rigtige rækkefølge, kan du ikke bruge et regulært udtryk til at fortælle, om en hel HTML-side er gyldig eller ej - fordi HTML ikke er et almindeligt mønster. ml >, ead>

Turing-maskiner

Så hvordan genkender du ikke-regelmæssige mønstre ?

Der er en teoretisk enhed, der ligner en statsmaskine, kaldet en Turing Machine. Det ligner en finite state-maskine, idet den har en papirstrimmel, som den læser. Men en Turing-maskine kan slette og skrive på papirbåndet.

At forklare en Turing-maskine vil tage mere plads, som vi har her, men der er et par vigtige punkter, der er relevante for vores diskussion af finite state-maskiner og regulære udtryk.

Turing Machines er beregningsmæssigt komplette - hvilket betyder alt, hvad der kan beregnes, kan beregnes på en Turing Machine.

Da en Turing-maskine kan skrive såvel som at læse fra papirbåndet, er den ikke begrænset til et begrænset antal stater. Papirbåndet kan antages at være uendelig i længden. Naturligvis har egentlige computere ikke uendelig meget hukommelse. Men de indeholder normalt nok hukommelse, så du ikke rammer grænsen for den type problemer, de behandler.

Turing Machines giver os en imaginær mekanisk enhed, der lader os visualisere og forstå, hvordan beregningsprocessen fungerer. Det er især nyttigt at forstå grænserne for beregning. Hvis der er interesse, laver jeg en anden artikel om Turing Machines i fremtiden.

Hvorfor betyder dette noget?

Så hvad er pointen? Hvordan vil dette hjælpe dig med at oprette den næste PHP-formular?

Uanset deres begrænsninger er statsmaskiner et meget centralt koncept for computing. Især er det vigtigt, at der for enhver ikke-deterministisk tilstandsmaskine, du kan designe, findes en deterministisk tilstandsmaskine, der gør det samme.

Dette er et nøglepunkt, fordi det betyder, at du kan designe din algoritme, uanset hvilken måde der er nemmest at tænke på. Når du har en fungerende algoritme, kan du konvertere den til den form, der er mest effektiv.

Forståelsen om, at finite state-maskiner og regulære udtryk er funktionelt ækvivalente, åbner nogle utroligt interessante anvendelser til regulære ekspressionsmotorer - især når det kommer til at skabe forretningsregler, der kan ændres uden at kompilere et system igen.

Et fundament inden for datalogi giver dig mulighed for at tage et problem, som du ikke ved, hvordan man løser og begrunder: ”Jeg ved ikke, hvordan man løser X, men jeg ved, hvordan man løser Y. Og jeg ved, hvordan man konverterer en løsning for Y til en løsning til X. Derfor ved jeg nu, hvordan man løser X. ”

Hvis du kan lide denne artikel, kan du nyde min YouTube-kanal, hvor jeg opretter en lejlighedsvis video eller tegneserie om et eller andet aspekt af oprettelse af software. Jeg har også en mailingliste til folk, der gerne vil lejlighedsvis e-mail, når jeg producerer noget nyt.

Oprindeligt offentliggjort på blog.markshead.com den 11. februar 2018.