Zimanek bê kontekst çawa tê pênase kirin, û pêkhateyên rêzimanek bê kontekst çi ne?
Zimanek bê konteks celebek zimanê fermî ye ku dikare bi karanîna rêzimanek bê-contekst were vegotin. Di warê teoriya tevliheviya hesabkerî de, zimanên bê kontekst di têgihîştina tevliheviya pirsgirêkan û sînorên hesabkirinê de rolek girîng dilîzin. Ji bo têgihîştina têgîna zimanek bê kontekst bi tevahî, pêdivî ye ku meriv pênaseya wî û pêkhateyên rêzimanek bê kontekst were lêkolîn kirin.
Zimanek bê kontekst wekî komek rêzikan tê pênase kirin ku dikare ji hêla rêzimanek bê kontekst ve were çêkirin. Rêzimanek bê kontekst ji çar beşan pêk tê: komek sembolên ne-termînalê, komek sembolên termînalê, komek rêzikên hilberînê, û nîşanek destpêkê.
Sembolên ne-termînalê hebûnên razber temsîl dikin ku dikarin bêtir bêne berfireh kirin an bi sembolên din veguhezînin. Ev sembol bi gelemperî bi tîpên mezin têne xuyang kirin. Mînakî, di rêzimanek bê konteks de ji bo biwêjên arithmetîk, dibe ku em xwedî sembolên ne-termînalê yên mîna E (nimûneya îfadeyekê), T (temsîlkirina termekê), û F (tewandîkirina faktorekê) hebin.
Ji aliyê din ve, sembolên termînalê, yekîneyên bingehîn ên zimên in. Ev sembol nikarin bêtir bêne berfireh kirin û bi gelemperî bi tîpên piçûk an tîpên din têne destnîşan kirin. Di çarçoweya biwêjên arithmetîk de, sembolên termînalê dibe ku jimare (mînak, 0, 1, 2) û operatorên jimartinê (mînak, +, -, *, /) bihewînin.
Rêzikên hilberandinê diyar dikin ka sembolên ne-termînalê çawa dikarin bi sembolên din werin berfireh kirin an li şûna wan werin guhertin. Her qaîdeyek hilberînê ji sembolek ne-termînalê li milê çepê û rêzek sembolan (hem ne-termînalê û hem jî termînalê) li milê rastê pêk tê. Van qaîdeyan veguherînên muhtemel an jêderkên ku dikarin werin sepandin ji bo çêkirina rêzikên derbasdar di ziman de diyar dikin. Mînakî, di rêzimanek bê çarçoveyek ji bo biwêjên arîtmetîk de, dibe ku me qaîdeyên hilberînê yên mîna E -> E + T (nîşan dide ku bi lêzêdekirina termekê vebêjek dikare were berfireh kirin) an T -> F (nîşan dide ku termek dikare were berfireh kirin) hebin. bi faktorek veguherî).
Nîşana destpêkê nîşana destpêkê ya ne-termînalê nîşan dide ku nifşa rêzikên derbasdar jê dest pê dike. Ew bi gelemperî bi S-yê tê destnîşan kirin. Di çarçoweya biwêjên arithmetîk de, nîşana destpêkê dibe ku E be, ev nîşan dide ku nifşa bêjeyên derbasdar ji bêjeyekê dest pê dike.
Ji bo ronîkirina têgeha zimanek bê kontekst û pêkhateyên wî, werin em rêzimanek bê kontekstek hêsan ji bo zimanek ku parantezên hevseng çêdike bihesibînin. Rêziman ji van hêmanan pêk tê:
Sembolên ne-termînalê: S (nîşana destpêkê)
Nîşaneyên termînalê: (, )
Rêbazên hilberînê: S -> (S) | SS | ε (ku ε rêza vala temsîl dike)
Di vê rêzimanê de, nîşana ne-dawî S rêzikek ji parantezên hevseng temsîl dike. Rêzikên hilberînê diyar dikin ku S dikare bi girtina S-ya din di nav parantezê ((S)) de, bi hev ve kirina du S-yan (SS) an jî çêkirina rêzika vala (ε) were berfireh kirin.
Bi bikaranîna vê rêzimanê, em dikarin rêzikên derbasdar bi zimanê parantezê hevseng çêkin. Mînakî, bi nîşana destpêkê S-yê dest pê dike, em dikarin qaîdeyên hilberînê bicîh bînin ku rêzika ((()) derxînin. Ev rêz rêzek ji parantezên hevseng temsîl dike.
Zimanek bê kontekst wekî komek rêzikan tê pênase kirin ku dikare ji hêla rêzimanek bê kontekst ve were çêkirin. Pêkhateyên rêzimanek bê-tewre sembolên ne-termînalê, sembolên termînalê, qaîdeyên hilberînê, û nîşanek destpêkê hene. Sembolên ne-termînalê hebûnên razber ên ku dikarin bêne berfireh kirin an veguheztin destnîşan dikin, dema ku sembolên termînalê yekîneyên bingehîn ên ziman in. Rêzikên hilberandinê veguhertinên muhtemel an jêderk diyar dikin, û nîşana destpêkê ji bo çêkirina rêzikên derbasdar sembola ne-termînalê ya destpêkê temsîl dike.
Pirs û bersivên din ên vê dawiyê di derbarê Zimanên Hêstiyar ên Naverok:
- Wateya wê çi ye ku zimanek ji yê din bi hêztir e?
- Rêzimana Chomsky ya normal her gav biryardar e?
- Ji bo naskirina Type-0 rêbazên heyî hene? Ma em li bendê ne ku komputerên quantum wê pêkan bikin?
- Di mînaka zimanê D de, çima taybetiya pompkirinê ji bo rêza S = 0^P 1^P 0^P 1^P nagire?
- Dema ku rêzek ji bo sepandina lemma pompkirinê tê dabeş kirin du doz çi ne?
- Di mînaka zimanê B de, çima taybetmendiya pompkirinê ji bo rêzika a^Pb^Pc^P nagire?
- Ji bo ku milkê pompê bigire divê şert û mercên çi ne?
- Çawa dikare Lemma Pumping ji bo CFL-an were bikar anîn da ku îspat bike ku zimanek ne bê kontekst e?
- Ji bo ku zimanek li gorî lemmaya pompeyî ya ji bo zimanên bê-kontekst bêtevger were hesibandin şert û mercên ku divê werin bicîh kirin çi ne?
- Di çarçoweya rêzimanên bê kontekst de têgeha vegerandinê rave bike û ka ew çawa rê dide çêkirina rêzikên dirêj.
Pirs û bersivan zêdetir di Zimanên Hessas Context de bibînin