Bi berçavgirtina PDA-yên ne-determînîst, lihevkirina dewletan ji hêla pênasê ve gengaz e. Lêbelê, PDA-yên ne-determînîst tenê stekek heye ku nekare bi hevdemî di gelek dewletan de be. Ev çawa gengaz e?

/ / Weşandin Pîroz, EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê, Pushdown Automata, Hevsengiya CFG û PDA-an

Ji bo çareserkirina pirsa di derbarê otomatên şûştinê yên ne-determînîst (PDA) û paradoksa diyar a serpêhatiya dewletê ya bi yek stûnê de, pêdivî ye ku meriv prensîbên bingehîn ên ne-determînîzmê û mekanîka xebitandinê ya PDA-yan bihesibîne.

Otomatona pushdown modelek hesabker e ku bi tevlêkirina navgînek hilanînê ya alîkar ku wekî stack tê zanîn kapasîteyên otomatên bêdawî berfireh dike. Ev stack otomatê bi şiyana hilanîna jimarek bêsînor agahiyê peyda dike, her çend bi awayê paşîn, yekem-derve (LIFO), ku ji bo naskirina zimanên bê çarenûs girîng e. Bi taybetî, otomatên şûştinê yên ne-determînîst (NPDA), vê modelê zêde dike bi rê dide veguheztinên pir muhtemel ên ji bo rewşek diyarkirî û sembola têketinê, dişibihe têgîna ne-determînîzmê di otomatên bêdawî de.

Têgîna ne-determînîzmê di çarçoweya PDA-yan de rasterast bi têgîna mekanîkî ya quantum a superposition re têkildar nîne. Di şûna wê de, ew behsa kapasîteya otomatê dike ku di heman demê de gelek rêyên hesabkerî bikole. Ev bi rê ve dibe ku otomatê di nav veguheztinên berdest de hilbijartinên keyfî bike. Dema ku NPDA bi xalek bijartî re rû bi rû bimîne, ew dikare "şaqê" bike nav gelek rêyên hesabkirinê de, ku her yek rêzek cûda ya veguheztina dewletê û operasyonên stackê temsîl dike.

Lêbelê, stack di nav her rêça hesabkirinê de hebûnek yekane dimîne. Di van rêyan de bi hevdemî di gelek dewletan de tune. Belê, her şaxek hesabkirinê guhertoya xweya serbixwe ya stackê diparêze. Ev serxwebûn ji bo NPDA girîng e ku bi hev re gelek hejmartinên potansiyel bi rêkûpêk simule bike. Dema dîtbarîkirina operasyona NPDA-yê, meriv dikare wê bifikire ku wekî strukturek wekî darê ya hesaban diparêze, ku her girêk veavakirinek yekta ya dewletê, pozîsyona têketinê, û naverokek stûnê temsîl dike.

NPDA-ya ku ji bo naskirina zimanê parantezên hevseng hatî çêkirin, bifikirin. Bihesibînin ku otomatê di rewşek de ye ku tê de parantezek vekirinê xwendiye û divê biryar bide ka wê bikişîne ser stikê an jî bêyî ku bikişîne derbasî rewşek din bibe. Bi rengek ne-determînîst, NPDA dikare her du vebijarkan bi hevdemî "hilbijêre", bi bandor du şaxên hesabkirinê biafirîne. Di şaxekê de, stêk paranteza vekirinê dihewîne, lê di ya din de, ew tune. Her şax li ser bingeha bijartina xweya destpêkê serbixwe pêş dikeve, digel ku naveroka stakê li gorî rêza taybetî ya operasyonan di wê şaxê de pêşve diçe.

Vê şiyana şaxkirinê dihêle NPDA-yan bi hev re gelek hîpotezan li ser strûktûra xêza têketinê bikolin. Ger bi kêmanî yek şaxek hesabkirinê berbi rewşek pejirandî ya bi stûnek vala ve bibe, NPDA têketinê qebûl dike. Ev şaxkirina ne-determînîst taybetmendiyek bi hêz e ku dihêle NPDA ji PDA-yên diyarker, bi taybetî hemî zimanên bê kontekst, çînek zimanek berfirehtir nas bike.

Têgeha ne-determînîzmê di PDA-yan de dikare bi vekolîna pênaseya fermî ya otomatê de ne-determînîst bêtir were ronî kirin. NPDA bi gelemperî wekî 7-tuple tête diyar kirin:

    \[ (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F) \]

ko:
- Q komeke dawî ya dewletan e.
- \Sigma alfabeya têketinê ye.
- \Gamma alfabeya stûyê ye.
- \delta fonksiyona veguherînê ye, ku nexşeyan dike Q \car (\Sigma \ cup \{\epsilon\}) \times \Gamma heta binekomeke dawî ya Q \time \Gamma^*.
- q_0 rewşa destpêkê ye.
- Z_0 sembola stûna destpêkê ye.
- F koma dewletên qebûlker e.

Fonksiyona veguherînê \delta Di PDA-yan de bingeha ne-determînîzmê ye. Ew ji bo rewşek diyarkirî, nîşana têketinê, û sembola jorîn a stackê destûrê dide veguheztinên pirjimar ên gengaz. Van veguheztinan dikarin derbasî rewşek nû bibin, nîşanek têketinê bixwin, û bi xistina sembolan an jî pêxistina stêkê biguhezînin. Hebûna \epsilon-Veguheztin (veguheztinên ku sembola têketinê naxwin) nermbûna NPDA-yan bêtir zêde dike û dihêle ku ew rewşan biguhezînin û stikê bêyî xwendina têketinê manîpule bikin.

Ji bo ronîkirinê, NPDA-ya hêsan a ku ji bo naskirina ziman hatî çêkirin bihesibînin L = \{ a^nb^n | n \geq 0 \}. Ev ziman ji rêzikên bi jimareke wekhev pêk tê a's li pey b's. NPDA bi vî awayî dixebite:
1. Di rewşeke destpêkê de dest pê dike q_0 bi sembola stack destpêkê Z_0.
2. Ji bo her yekê a ji têketinê dixwîne, ew an dehf dike X li ser stackê, veguherîna dewletê q_1.
3. Li ser rûbirûbûna a b, derdikeve an X ji stackê, veguherîna dewletê q_2.
4. NPDA dipejirîne eger ew bigihîje rewşek pejirandî ya ku stûna wê vala ye piştî ku tevaya têketinê bişopîne.

Aliyê ne-determînîst destûrê dide NPDA ku dozên ku rêzika têketinê li gorî şêwaza bendewariyê nagunce bi rê ve bibe. Mînakî, heke rêzika têketinê zêdetir hebe b's ji a's, stack dê berî dawiya têketinê vala bibe, ku bibe sedema redkirinê. Alternatîf, heke bêtir hene a's ji b's, steck dê piştî hilberandina têketinê vala nemîne, di encamê de were red kirin.

Rêbaza sereke ev e ku ne-determînîzm di PDA-yan de dihêle ku otomatê li gelek rêçên hesabkerî bigere bêyî ku hewce bike ku stack bi hevdemî di gelek dewletan de be. Her rêyek veavakirina stackê ya xwe diparêze, ku dihêle NPDA bi hev re hesabên cûda yên potansiyel simule bike. Vê kapasîteyê ew e ku destûrê dide NPDA-yan ku zimanên bê-contek bi bandor nas bikin.

Di eslê xwe de, stûna yekane ya di NPDA de ne sînorek e, lê taybetmendiyek e ku vekolîna ne-determînîst a rêyên hesabkirinê piştgirî dike. Bi domandina veavakirinên stûnê yên cihêreng ên ji bo her şaxek hesabkirinê, NPDA dikare gelek hîpotezan di derbarê strukturê rêzika têketinê de binirxîne, di dawiyê de diyar bike ka stêr girêdayî zimanê ku ji hêla otomatê ve hatî nas kirin e.

Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:

Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin

Pirs û bersivên bêtir:

Tagged under: , , , , ,