Ma em dikarin diyar bikin ka rêzikek diyarkirî ji hêla rêzimanek bê kontekst ve tê pejirandin? Ma ev pirsgirêk çareser dibe?
Tesbîtkirina ka rêzikek diyarkirî ji hêla rêzimanek bê kontekst ve tê pejirandin pirsgirêkek bingehîn e di teoriya tevliheviya hesabkirinê de. Ev pirsgirêk dikeve binê kategoriya berfireh a biryardariyê, ya ku bi destnîşankirina ka malek taybetî ji bo têketinek diyarkirî digire. Di warê rêzimanên bê kontekst de, pirsgirêka pejirandina rêzikê bi rastî jî biryardar e.
Rêzimana bê kontekst pergalek fermî ye ku ji komek qaîdeyên hilberînê pêk tê ku diyar dike ka meriv çawa rêzikên di zimanekî de çê dike. Ew bi tîpek (V, Σ, R, S) tê destnîşankirin, ku V komek sembolên ne-termînalê ye, Σ komek sembolên termînalê ye, R komek rêzikên hilberînê ye, û S sembola destpêkê ye. Zimanê ku ji hêla rêzimanek bê kontekst ve hatî çêkirin komek hemî rêzikên ku dikarin ji nîşana destpêkê bi karanîna qaîdeyên hilberînê werin derxistin.
Ji bo destnîşankirina ka rêzikek diyarkirî ji hêla rêzimanek bê kontekst ve tê pejirandin, em dikarin algorîtmayên cihêreng bikar bînin, wek algorîtmaya CYK an algorîtmaya Earley. Van algorîtmayan teknîkên bernamesaziya dînamîkî bi kar tînin da ku bi bandor kontrol bikin ka rêzek dikare ji sembola destpêkê ya rêzimanê were derxistin.
Mînakî, algorîtmaya CYK, tabloyek ava dike ku her şaneyek binerêzek rêzika têketinê û komek ne-termînalên ku dikarin wê binerdê biafirînin temsîl dike. Bi dagirtina dubare ya tabloyê li ser bingeha rêzikên hilberîna rêzimanê, algorîtma diyar dike ka nîşana destpêkê dikare tevahiya rêzika têketinê çêbike. Heke nîşana destpêkê di şaneya jorîn-rast a tabloyê de xuya bibe, wê hingê rêzik ji hêla rêzimanê ve tê pejirandin; wekî din, ew nabe.
Mînaka jêrîn binihêrin: Ka em bibêjin ku rêzimanek me ya bê kontekst bi qaîdeyên hilberînê heye:
S -> AB
A -> a
B -> b
Ger em bixwazin diyar bikin ka rêzika "ab" ji hêla vê rêzimanê ve tê pejirandin an na, em dikarin algorîtmaya CYK bicîh bînin. Algorîtm tabloyek bi du şaneyan ava dike, yek ji bo her karakterek di rêzika têketinê de. Tablo wiha xuya dike:
| 1 | 2 |
—+—+—+
1 | A | S |
—+—+—+
2 | | B |
—+—+—+
Ji rêza jêrîn dest pê dike, em dikarin bibînin ku di şaneya (2,2) de ne-termînala B heye, ku ji hêla qaîdeya hilberînê B -> b ve hatî çêkirin. Ber bi rêza jorîn ve diçin, em dibînin ku şaneya (1,2) S-ya ne-termînalê heye, ku ji hêla qaîdeya hilberînê S -> AB ve hatî çêkirin. Di dawiyê de, di şaneya (1,1) de A-ya ne-termînalê heye, ku ji hêla qaîdeya hilberînê A -> a ve hatî çêkirin. Ji ber ku nîşana destpêkê S di şaneya jorîn-rastê de xuya dike, em dikarin encam bidin ku rêzika "ab" ji hêla rêzimanê ve tê pejirandin.
Pirsgirêka destnîşankirina ka rêzikek diyarkirî ji hêla rêzimanek bê-contekst ve tê pejirandin, biryardar e. Algorîtmayên wekî algorîtmaya CYK an algorîtmaya Earley dikare were bikar anîn da ku bi rengek bikêr were kontrol kirin ka rêzek dikare ji sembola destpêkê ya rêzimanê were derxistin. Van algorîtmayan teknîkên bernamesaziya dînamîkî bikar tînin da ku tabloyan çêbikin û pejirandina rêzikê diyar bikin.
Pirs û bersivên din ên vê dawiyê di derbarê Biryardarî:
- Ma kasetek dikare bi mezinahiya têketinê ve were sînordar kirin (ku wekhev e ku serê makîneya turingê bi sînorkirî ye ku ji têketina kasêta TM-yê wêdetir bimeşe)?
- Wateya guhertoyên cihêreng ên Makîneyên Turing di kapasîteya hesabkirinê de tê çi wateyê?
- Ma zimanek naskirî dikare binekomek zimanê biryardar pêk bîne?
- Pirsgirêka rawestandina makîneyek Turing biryardar e?
- Ger du TM-yên me hene ku zimanek biryardar diyar dikin, gelo pirsa wekheviyê hîn jî nayê biryar?
- Pirsgirêka pejirandinê ji bo otomatên xêzkirî ji ya makîneyên Turing çawa cûda dibe?
- Mînakek pirsgirêkek bide ku dikare ji hêla otomatek sînorkirî ya xêz ve were biryardan.
- Di çarçoweya otomatên sînorkirî yên rêzê de têgeha biryardarbûnê rave bikin.
- Mezinahiya kasêtê di otomatên xêzkirî de çawa bandorê li hejmara veavakirinên cihê dike?
- Cûdahiya sereke di navbera otomatên sînorkirî yên rêzkirî û makîneyên Turing de çi ye?
Pir pirs û bersivan di Decidability de bibînin