Zimanên birêkûpêk çawa dikarin bi karîgerî bêne nasîn û parkirin?
Zimanên bi rêkûpêk di teoriya tevliheviya hesabkerî de têgehek bingehîn e û di warên cihêreng ên zanistiya komputerê de, tevî ewlehiya sîber, rolek girîng dileyze. Naskirin û parskirina zimanên birêkûpêk bi bandor di gelek serlêdanan de girîngiyek mezin e, ji ber ku ew dihêle ku pêvajoyek bi bandor a daneyên sazkirî û tespîtkirina qalibên di rêzan de were girtin.
Ji bo naskirina zimanên bi rêkûpêk bi bandor, gelek algorîtm û teknîk hatine pêşve xistin. Yek nêzîkatiyek ku pir tê bikar anîn karanîna otomatên dawîn ên diyarker (DFA) ye. DFA modelek matematîkî ye ku ji komek sînorkirî ya dewletan û veguherînên di navbera van dewletan de li ser bingeha sembolên têketinê pêk tê. Ew dikare rêzek bipejirîne an red bike li ser bingeha ka ew digihîje rewşek pejirandinê piştî ku tevahiya têketinê hildibijêre.
Pêvajoya naskirinê di DFA de rasterast û bikêrhatî ye. Ji rêzek tê dayîn, DFA di rewşek destpêkê de dest pê dike û sembolên têketinê yek bi yek dixwîne, di navbera dewletan de li gorî veguheztinên ku di DFA-yê de hatine destnîşan kirin veguherîne. Ger, piştî hilberandina tevahiya rêzê, DFA di rewşek pejirandinê de be, rêz tê pejirandin; wekî din, ew tê red kirin. Tevliheviya demê ya naskirina rêzek bi karanîna DFA-yê di dirêjahiya têketinê de xêz e.
Nêzîkatiyek din a bikêr a naskirina zimanên rêkûpêk bi karanîna bêjeyên birêkûpêk e. Vebêja birêkûpêk ji bo danasîna qalibên di rêzan de nîşanek kurt û diyarker e. Ew dikare wekî formulek ku komek rêzan diyar dike were fikirîn. Gotinên birêkûpêk dikarin bi karanîna algorîtmaya avakirinê ya Thompson veguhezînin NFA-yan (otomatên dawîn ên ne diyarker). Dûv re ev NFA dikarin bi karanîna algorîtmaya avakirina hêzê bi bandor li DFA-yan werin veguheztin.
Dema ku zimanek birêkûpêk were nas kirin, parsing dikare were kirin da ku agahdariya watedar ji têketinê derxîne. Parsandin analîzkirina strukturên rêzikan li gorî rêzimanek diyarkirî vedihewîne. Ji bo zimanên birêkûpêk, parsing ji ber tevliheviya sînorkirî ya ziman bi nisbî hêsan e. Teknîka parskirinê ya herî gelemperî ya ji bo zimanên birêkûpêk nêzîkatiya "çep-rast-rast, herî dirêj-hev" tê binavkirin. Ev nêzîkatî rêzika têketinê ji çepê ber bi rastê ve dişoxilîne, di her gavê de binesaziya herî dirêj a gengaz li hev dike. Ew bikêr e û dikare bi karanîna DFA an NFA-yê were bicîh kirin.
Bi kurtasî, zimanên birêkûpêk dikarin bi karanîna teknîkên wekî otomatên dawîn ên diyarker (DFA), bilêvkirinên birêkûpêk, û nêzîkatiya parskirina ji çep-rast, ya herî dirêj-dirêj, bi bandor werin nas kirin û parkirin. Van rêbazan algorîtmayên bikêrhatî peyda dikin ji bo hilberandina daneya birêkûpêk, tespîtkirina nimûneyan, û derxistina agahdariya watedar ji rêzan.
Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:
- Dema ku PDA-ya ku dikare palindroman bixwîne bihesibîne, gelo hûn dikarin geşedana stikê bi hûrgulî hûrgulî bikin dema ku têketin, yekem, palindromek, û ya duyemîn jî, ne palindrom be?
- 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?
- Mînaka PDA-yan çi ye ku ji bo analîzkirina seyrûsefera torê û nasîna qalibên ku binpêkirinên ewlehiyê yên potansiyel destnîşan dikin tê bikar anîn?
- Wateya wê çi ye ku zimanek ji yê din bi hêztir e?
- Ma zimanên hesas ên kontekstê ji hêla Makîneya Turing ve têne nas kirin?
- Çima ziman U = 0^n1^n (n>=0) ne rêkûpêk e?
- Meriv çawa FSM rêzikên binary bi hêjmarên '1' yên zewac nas dike pênase bike û nîşan bide ku dema ku rêzika têketinê 1011 hildiweşîne çi diqewime?
- Nedetermînîzm çawa bandorê li fonksiyona veguherînê dike?
- Ma zimanên birêkûpêk bi Makîneyên Dewleta Dawî re hevwate ne?
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin