Riigimasinate mõistmine

Sissejuhatus arvutiteaduse kontseptsioonidesse

Arvutiteadus võimaldab meil programmeerida, kuid on võimalik palju programmeerida, mõistmata aluseks olevaid arvutiteaduse mõisteid.

See pole alati halb asi. Programmeerides töötame palju abstraktsemal tasemel.

Autoga sõites muretseme end ainult kahe või kolme pedaali, käiguvahetuse ja rooliga. Autot saab ohutult käsitseda, ilma et oleks aimu selle toimimisest.

Kui soovite aga autot juhtida selle võimaluste piires, peate autode kohta tundma palju muud kui ainult kolme pedaali, käiguvahetust ja rooli.

Sama lugu on programmeerimisega. Palju igapäevatööd saab teha arvutiteaduse vähese mõistmisega või üldse mitte. PHP-s vormi "Võtke meiega ühendust" loomiseks ei pea te arvutusteooriast aru saama.

Kui plaanite kirjutada tõsist arvutamist vajavat koodi, peate siiski natuke rohkem aru saama, kuidas arvutamine kapoti all töötab.

Selle artikli eesmärk on anda arvutamiseks mõned põhimõttelised taustad. Huvi korral võin järgida mõningaid edasijõudnumaid teemasid, kuid tahan praegu vaadata ühe lihtsama abstraktse arvutusvahendi - lõpliku olekumasina - loogikat .

Lõplike olekute masinad

Lõpliku olekuga masin on matemaatiline abstraktsioon, mida kasutatakse algoritmide kujundamiseks.

Lihtsamalt öeldes loeb olekumasin rea sisendeid. Kui see loeb sisendit, lülitub see teise olekusse. Iga olek täpsustab, millisesse olekusse antud sisendi jaoks lülituda. See kõlab keeruliselt, kuid on tegelikult üsna lihtne.

Kujutage ette seadet, mis loeb pikka paberit. Iga tolli paberi kohta on sellele trükitud üks täht - kas täht „a” või „b”.

Kui riigimasin loeb iga tähte, muudab see olekut. Siin on väga lihtne olekumasin:

Ringid on olekud , milles masin võib olla. Nooled on üleminekud . Seega, kui olete olekus s ja loete tähte „a”, lähete üle olekusse q . Kui loete tähte „b”, jääte osariiki s .

Nii et kui alustame s-st ja loeme ülalt vasakult paremale paberilinti, siis loeme tähte "a" ja liigume olekusse q .

Seejärel loeme tähe „b” ja liigume tagasi olekusse s .

Teine 'b' hoiab meid s-l , millele järgneb 'a' - mis viib meid tagasi q- olekusse. Piisavalt lihtne, aga mis mõtet sellel on?

Noh, selgub, et saate linti läbi olekumasina ja rääkida midagi tähtede järjestusest, uurides olekut, kuhu sattute.

Kui meie ülaltoodud lihtsas olekumasinas lõpeb olek s , peab lint lõppema tähega 'b'. Kui lõpetame oleku q , lõpeb lint a-tähega.

See võib tunduda mõttetu, kuid seda tüüpi lähenemisviisidega saab lahendada kohutavalt palju probleeme. Väga lihtne näide oleks teha kindlaks, kas HTML-i leht sisaldab neid silte selles järjekorras:

Olekumasin saab liikuda olekusse, mis näitab, et ta on lugenud html-märgendit, tsüklit, kuni jõuab peamärgini, silmust, kuni jõuab peasulgemissildini jne.

Kui see jõuab edukalt lõplikku olekusse, on teil need märgendid õiges järjekorras.

Lõplike olekuga masinaid saab kasutada ka paljude teiste süsteemide - näiteks parkimiskella mehaanika, popmasina, automatiseeritud gaasipumba ja igasuguste muude asjade - esindamiseks.

Deterministlikud lõpliku oleku masinad

Olekumasinad, mida seni oleme vaadanud, on kõik deterministlikud olekumasinad. Igast olekust on lubatud sisendi jaoks ainult üks üleminek. Teisisõnu, a-tähe lugemisel ei saa olla kahte teed, mis viib olekust välja. Alguses kõlab see jabur, et isegi seda vahet teha.

Mis kasu on otsuste kogumist, kui sama sisendi tulemusel võib liikuda rohkem kui ühte olekusse? Kas ei saa arvutile öelda, if x == truesiis käivitada doSomethingBigvõi täita doSomethingSmall?

Noh, riigimasinaga saate kuidagi.

Olekumasina väljund on selle lõppseisund. See läbib kogu selle töötlemise ja seejärel loetakse lõplik olek ning seejärel võetakse ette toiming. Riigimasin ei tee riigist teise liikudes midagi.

See töötleb ja kui see lõpuni jõuab, loetakse olek läbi ja miski väline käivitab soovitud toimingu (näiteks soodakannu väljastamine). See on oluline mõiste, kui tegemist on mitte-deterministlike lõplike olekumasinatega.

Mittemääravad lõpliku oleku masinad

Mittemäärajad lõplike olekute masinad on piiratud olekuga masinad, kus konkreetse oleku antud sisend võib viia rohkem kui ühe erineva olekuni.

Oletame näiteks, et tahame ehitada lõpliku olekumasina, mis suudaks ära tunda tähti, mis:

  • Alustage a-tähega
  • ja neile järgneb null või rohkem tähte "b"
  • või null või enam tähte „c”
  • lõpetatakse tähestiku järgmise tähega.

Kehtivad stringid oleksid:

  • abbbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac (b esinemise null esinemist)
  • ad (null esinemist c)

Nii tunneb see ära tähe „a”, millele järgneb null või rohkem sama tähte „b” või „c”, millele järgneb järgmine tähestiku täht.

Selle esitamiseks on väga lihtne viis olekumasinaga, mis näeb välja nagu allpool olev, kus t lõplik olek tähendab, et string aktsepteeriti ja vastab mustrile.

Kas näete probleemi? Alguspunktist s me ei tea, millist teed minna. Kui loeme a-tähte, ei tea me, kas minna osariiki q või r.

Selle probleemi lahendamiseks on mõned võimalused. Üks on tagasiteel. Te lihtsalt lähete kõikvõimalikel radadel ja ignoreerite või taganete nendest, kuhu te kinni jääte.

Põhimõtteliselt töötab enamik malet arvutit mängides. Nad vaatavad kõiki võimalusi - ja nende võimaluste kõiki võimalusi - ja valivad tee, mis annab neile vastase ees kõige rohkem eeliseid.

Teine võimalus on mitte-deterministliku masina teisendamine deterministlikuks masinaks.

Mitte-deterministliku masina üks huvitav atribuut on see, et eksisteerib algoritm mis tahes mittemäärava masina muutmiseks deterministlikuks. Sageli on see aga palju keerulisem.

Meie õnneks on ülaltoodud näide vaid veidi keerulisem. Tegelikult on see üks piisavalt lihtne, et saaksime selle transformeerida oma peas deterministlikuks masinaks, ilma ametliku algoritmi abita.

Allpool olev masin on ülaltoodud deterministliku masina deterministlik versioon. Allpool toodud masinas saavutatakse t või v lõplik olek mis tahes masina poolt aktsepteeritud stringiga.

Mittemäärav mudelil on neli olekut ja kuus üleminekut. Deterministlikul mudelil on kuus olekut, kümme üleminekut ja kaks võimalikku lõppseisundit.

See pole nii palju rohkem, kuid keerukus kasvab tavaliselt hüppeliselt. Mõõduka suurusega mitte-deterministlik masin võib toota absoluutselt tohutu deterministliku masina.

Regulaaravaldised

Kui olete mõnda tüüpi programmeerimist teinud, olete tõenäoliselt kohanud regulaaravaldisi. Regulaaravaldised ja piiratud olekumasinad on funktsionaalselt samaväärsed. Kõike, mida saate tavalise avaldisega aktsepteerida või sobitada, saab aktsepteerida või sobitada olekumasinaga.

Näiteks võiks ülalkirjeldatud mustri sobitada regulaaravaldisega: a(b*c|c*d)

Regulaaravaldistel ja piiratud olekumasinatel on samuti samad piirangud. Eelkõige saavad nad mõlemad sobitada või aktsepteerida ainult mustreid, mida saab käsitleda piiratud mäluga.

Mis tüüpi mustreid nad ei saa omavahel sobitada? Oletame, et soovite sobitada ainult 'a' ja 'b' stringe, kus on arv a-sid, millele järgneb võrdne arv b-sid. Või n 'a, millele järgneb n ' b, kus n on mingi arv.

Näiteks on:

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

Esialgu näib see piiratud riigimasina jaoks lihtne töö. Probleem on selles, et olekud saavad kiiresti otsa või peate eeldama lõpmatu arvu olekuid - sel hetkel pole see enam lõplik olekumasin.

Oletame, et loote lõpliku olekumasina, mis suudab vastu võtta kuni 20 'a, millele järgneb 20' b. See töötab hästi, kuni saate 21 'a-ga stringi, millele järgneb 21' b - sel hetkel peate oma masina pikema stringi käsitsemiseks ümber kirjutama.

Mis tahes stringi jaoks, mille tunnete ära, on üks natuke pikem, mida teie masin ei tunne ära, kuna mälu saab otsa.

Seda tuntakse Pumping Lemma nime all, mis ütleb põhimõtteliselt: „kui teie mustril on sektsioon, mida saab korrata (nagu ülaltoodud), siis pole muster korrapärane”.

Teisisõnu, ei regulaaravaldise ega Äärellinen masin saab konstrueerida, mis tunnistavad kõik stringid et ei sobi muster.

Hoolikalt vaadates märkate, et seda tüüpi muster, kus igal a-l on vastav b, näeb välja väga sarnane HTML-iga. Igas sildipaaris võib teil olla suvaline arv muid sobituvaid silte.

Nii et ehkki saate kasutada regulaaravaldist või piiratud olekumasinat, et tuvastada, kas HTML-i lehel on ; ja elemendid õiges järjekorras, ei saa tavalise avaldise abil öelda, kas terve HTML-leht on kehtiv või mitte - kuna HTML pole tavaline muster. ml >, ead>

Turingi masinad

Kuidas siis ebaregulaarsed mustrid ära tunda ?

On olemas teoreetiline seade, mis sarnaneb olekumasinaga, mida nimetatakse Turingi masinaks. See sarnaneb piiratud olekuga masinaga, kuna sellel on pabeririba, mida ta loeb. Kuid Turingi masin saab paberilindilt kustutada ja kirjutada.

Turingi masina selgitamine võtab siin rohkem ruumi, kuid lõplike olekumasinate ja regulaaravaldiste arutelul on mõned olulised punktid.

Turingi masinad on arvutuslikult täielikud - see tähendab kõike, mida saab arvutada ja mida saab Turingi masinal arvutada.

Kuna Turingi masin suudab nii paberilindilt kirjutada kui ka lugeda, ei piirdu see piiratud arvu olekutega. Võib eeldada, et paberilindi pikkus on lõpmatu. Muidugi pole tegelikel arvutitel lõpmatult palju mälu. Kuid need sisaldavad tavaliselt piisavalt mälu, nii et te ei ületa nende töödeldavate probleemide piiri.

Turingi masinad annavad meile kujuteldava mehaanilise seadme, mis võimaldab meil arvutusprotsessi toimimist visualiseerida ja mõista. See on eriti kasulik arvutuspiiride mõistmisel. Kui on huvi, teen tulevikus veel ühe artikli Turingi masinate kohta.

Miks see oluline on?

Mis on selle mõte? Kuidas aitab see teil luua järgmist PHP-vormi?

Hoolimata nende piirangutest on olekumasinad arvutamisel väga keskne mõiste. Eelkõige on märkimisväärne, et mis tahes kujundatava mittemäärava olekumasina jaoks on olemas deterministlik olekumasin, mis teeb sama.

See on põhipunkt, sest see tähendab, et saate oma algoritmi kujundada sellisel viisil, millele on kõige lihtsam mõelda. Kui teil on toimiv algoritm, saate selle teisendada mis tahes kujul, mis on kõige tõhusam.

Arusaam, et piiratud olekumasinad ja regulaaravaldised on funktsionaalselt samaväärsed, avab regulaaravaldiste mootorite jaoks uskumatult huvitavaid kasutusviise, eriti kui tegemist on ärireeglite loomisega, mida saab muuta ilma süsteemi uuesti kompileerimata.

Arvutiteaduse sihtasutus võimaldab teil võtta probleemi, mida te ei oska lahendada, ja põhjendada seda: „Ma ei tea, kuidas lahendada X-i, aga tean, kuidas Y-d lahendada. Ja ma tean, kuidas lahendust teisendada Y-st X-i lahendiks. Seetõttu tean nüüd, kuidas X-i lahendada. "

Kui teile see artikkel meeldib, võiksite nautida minu YouTube'i kanalit, kus ma loon aeg-ajalt video või koomiksi tarkvara loomise mõnest aspektist. Mul on ka meililist inimeste jaoks, kes sooviksid aeg-ajalt meilisõnumeid, kui ma midagi uut toodan.

Algselt avaldati aadressil blog.markshead.com 11. veebruaril 2018.