Ma zimanên hesas ên kontekstê ji hêla Makîneya Turing ve têne nas kirin?
Zimanên hesas-contekst (CSL) çînek zimanên fermî ne ku ji hêla rêzimanên hesas-contekst ve têne diyar kirin. Van rêzimanan giştîkirina rêzimanên bê kontekst in, rê dide qaîdeyên hilberînê ku dikarin rêzek bi rêzek din biguhezînin, bi şertê ku veguheztin di çarçoveyek taybetî de pêk were. Ev çîna zimanan di teoriya hesabkirinê de girîng e ji ber ku ew ji zimanên bê-contekst bi hêztir e lê ji zimanên ku bi paşvegerî têne hejmartin kêmtir hêzdar e.
Pirsa ka gelo zimanên hesas ên kontekstê ji hêla Makîneya Turing ve têne nas kirin ji bo têgihiştina kapasîteyên û sînorên modelên hesabkerî navendî ye. Ji bo çareserkirina vê yekê, girîng e ku meriv pênasîn û taybetmendiyên hem zimanên hesas ên kontekstê û hem jî Makîneyên Turing binirxîne.
Makîneya Turing modelek hesabkerî ya razber e ku ji kasetek bêdawî, serê kasetek ku dikare sembolan bixwîne û binivîsîne, û komek rewşan a bêdawî pêk tê. Ew bi veguheztina di navbera dewletan de li gorî rêzek rêzik li ser bingeha rewşa heyî û sembola ku tê xwendin tevdigere. Makîneyên Turing bi şiyana xwe ya simulasyona her algorîtmayê, ya ku di teza Church-Turing de vegirtî ye, têne zanîn. Ev tez destnîşan dike ku her fonksiyonek ku bi algorîtmîkî were hesibandin dikare ji hêla Makîneyek Turing ve were hesibandin.
Zimanên hestiyar ên hevoksaziyê bi rêzimanên hestiyar ên kontekstê têne diyarkirin, ku qaîdeyên hilberînê yên forma αAβ → αγβ hene, ku A ne-termînalek e, û α, β, û γ rêzikên termînalan û/an ne-termînalan in. Astengiya sereke ev e ku dirêjahiya têlê li milê rastê divê herî kêm bi qasî têla milê çepê be. Ev piştrast dike ku zimanê ku hatî çêkirin ne-peymandar e, tê vê wateyê ku veqetandin nikarin dirêjiya rêzan kêm bikin.
Çîna zimanên ku ji hêla Turing Machines ve têne nas kirin, çîna zimanên ku bi paş ve têne hejmartin e. Zimanek bi vegerî tê hejmartin ger Makîneyek Turing hebe ku dê her rêzek di ziman de qebûl bike û li ser rêzikên ne di ziman de bêdawî bisekine an jî biqede. Zimanên hesas ên naverokê binekomek zimanên ku bi paşvekêşî têne hejmartin in, tê vê wateyê ku her zimanek hestiyar ji hêla Makîneya Turing ve tê naskirin.
Ji bo ku vê yekê nîşan bidin, Otomatîkek Rêzikkirî (LBA), ku formek sînorkirî ya Makîneyek Turing e, bihesibînin. LBA makîneyek Turingê ya ne-determînîst e ku bi kasetek ku ji hêla hin fonksiyonek rêzikî ya mezinahiya têketinê ve tê sînorkirin e. Ev sînorkirin tê vê wateyê ku LBA nikare ji ya ku pêdivî ye bêtir kaset bikar bîne da ku rêzika têketinê û hejmarek bêdawî ya agahdariya alîkar hilîne. Zimanên hesas ên naverokê bi rastî çîna zimanên ku ji hêla LBA ve têne pejirandin in. Ji ber ku LBA celebek Makîneya Turing e, her çend bi karanîna kasêta sînorkirî be jî, ji ber vê yekê dişoxilîne ku zimanên hestiyar ji hêla Makîneyên Turing ve têne nas kirin.
Ev kapasîteya naskirinê ji vê yekê derdikeve ku Makîneyek Turing dikare LBA-yê simule bike. Her çend LBA li ser karanîna kasêtê xwedan astengî ye jî, Makîneyek Turing dikare vê tevgerê bi karanîna dewletên din ji bo şopandina sînorên kasêtê simule bike. Ev simulasyon piştrast dike ku Makîneya Turing wekî LBA tevdigere, bi vî rengî zimanên hesas ên kontekstê nas dike.
Ji bo hê bêtir nîşan bide, zimanê L = { a^nb^nc^n | n ≥ 1 }, ku mînakek klasîk a zimanek hestiyar-kontekst e. Ev ziman nikare ji hêla rêzimanek bê kontekst ve were çêkirin, ji ber ku rêzimanên bê-conteks ne xwedî kapasîteya ku girêdayîbûna di navbera çend beşên rêzikê de bicîh bikin. Lêbelê, ew dikare bi rêzimanek hestiyar-contekst bi qaîdeyên wekî S → aSBc | abc û Bc → bC, di nav yên din de. LBA dikare were çêkirin da ku vî zimanî nas bike bi karanîna kasêta wî ya sînorkirî ji bo şopandina hejmarên 'a', 'b' û 'c', û piştrast bike ku ew wekhev in.
Qabiliyeta Makîneya Turing a naskirina zimanên hesas ên kontekstê ne tenê teorîkî ye, lê di zimannasiya hesabkerî û zimanên bernamesaziyê de xwedî bandorên pratîkî ye. Gelek zimanên bernamesaziyê xwedan avahîyên hevoksazî yên ku li ser kontekstê hesas in, pêdivî bi teknîkên parskirinê hene ku ji rêzimanên bê-conteks derbas dibin. Makîneyên Turing, bi gelemperîbûna xwe, çarçoveyek ji bo têgihiştin û bicihanîna parsekên van zimanan peyda dikin.
Di teoriya tevliheviya hesabkerî de, zimanên hesas ên kontekstê bi çîna tevliheviyê PSPACE re têkildar in. Ev çîn ji pirsgirêkên biryarê pêk tê ku dikarin ji hêla Makîneyek Turing ve bi karanîna cîhê pirnomîal ve werin çareser kirin. Naskirina zimanên hesas ên kontekstê ji hêla Turing Machines ve bi vê çîna tevliheviyê re têkildar e, ji ber ku LBA-yên ku van zimanan nas dikin, di nav sînorên cîhê pirnomîal de tevdigerin.
Zimanên hesas ên naverokê bi rastî ji hêla Turing Machines ve têne nas kirin. Ev nasîn ji hêla şiyana Makîneyên Turing ve ji bo simulasyona Linear Bounded Automata, yên ku bi taybetî hatine sêwirandin ji bo pejirandina zimanên hesas ên kontekstê têne çêkirin, hêsan dike. Ev têkilî hêz û nermbûna Makîneyên Turing di warê teoriya zimanê fermî û tevliheviya hesabkirinê de destnîşan dike.
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?
- Ç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?
- Li gorî Teza Church-Turing pirsgirêka ku ji hêla algorîtmîkî ve tê hesibandin pirsgirêkek e ku ji hêla Makîneyek Turing ve tê hesibandin?
Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin