Çima ziman U = 0^n1^n (n>=0) ne rêkûpêk e?

/ / Weşandin Pîroz, EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê, Pushdown Automata, PDA: Otomatîkên Pushdown

Pirsa ku ziman U = \{0^n1^n \mid n \geq 0\} birêkûpêk e an na mijarek bingehîn e di warê teoriya tevliheviya hesabkirinê de, nemaze di lêkolîna zimanên fermî û teoriya otomatê de. Têgihîştina vê têgehê pêdivî bi têgihîştina pênas û taybetmendiyên zimanên birêkûpêk û modelên hesabker ên ku wan nas dikin hewce dike.

Zimanên Birêkûpêk û Otomatên Dawî

Zimanên bi rêkûpêk çînek zimanan in ku dikarin ji hêla otomatên dawî ve werin nas kirin, ku makîneyên razber ên bi hejmarek dewletan ve girêdayî ne. Ev ziman dikarin bi karanîna bêjeyên rêkûpêk jî werin ravekirin û dikarin bi rêzimanên rêkûpêk werin çêkirin. Taybetmendiya sereke ya zimanên birêkûpêk ev e ku ew dikarin ji hêla otomatên dawî yên diyarker (DFA) an otomatên dawîn ên nedetermînîst (NFA) ve bêne nas kirin. DFA ji komek dewletan a bêdawî, komek sembolên têketinê, fonksiyonek veguhêz a ku cotên dewlet-sembolê bi dewletan re nexşe dike, rewşek destpêkê, û komek dewletên qebûlkirî pêk tê.

Hêza otomatên bêdawî ji hêla bîranîna wan ve sînorkirî ye. Ew nikarin ji hejmareke sabît bijmêrin, ku tê vê wateyê ku ew nikanin hejmareke keyfî ya bûyerên sembolek taybetî bişopînin heya ku hejmar bi hejmara dewletên di otomatê de were sînordar kirin. Dema ku meriv li ser zimanên weha têne hesibandin ev sînor girîng e U = \{0^n1^n \mid n \geq 0\}.

Ne-rêkûpêk ya U = \{0^n1^n \mid n \geq 0\}

Ji bo destnîşankirina ka zimanek rêkûpêk e, mirov dikare ji bo zimanên rêkûpêk Lemmaya Pumping bikar bîne. Lemma Pumping taybetmendiyek peyda dike ku divê hemî zimanên rêkûpêk têr bikin, û ew pir caran tê bikar anîn da ku nîşan bide ku hin ziman ne rêkûpêk in bi nîşandana ku ew vê taybetmendiyê têr nakin.

The Pumping Lemma diyar dike ku ji bo her zimanek birêkûpêk L, dirêjahiya pompkirinê heye p \geq 1 wisa ku her têl s in L bi dirêjahî |s| \geq p dikare bibe sê beş, s = xyz, şertên jêrîn têr dike:
1. |xy| \leq p,
2. |y| \geq 1, û
3. ji bo hemû i \geq 0, têl xy^iz in L.

Ji bo ku nîşan bide Lemma Pumping bikar bînin U = \{0^n1^n \mid n \geq 0\} ne bi rêkûpêk e, ji bo nakokiya ku U rêkûpêk e. Dûv re, dirêjahiya pompkirinê heye p wisa ku her têl s in U bi |s| \geq p dikare li beşan were dabeş kirin x, y, z têrkirina şert û mercên Lema Pumping.

Têlê bifikirin s = 0^p1^p in U. Li gorî Pumping Lemma, s dikare were parçe kirin x, y, z vî awayî |xy| \leq p û |y| \geq 1. Ji ber |xy| \leq p, binerd y tenê ji 0-an pêk tê. Ji ber vê yekê, x = 0^a, y = 0^b, û z = 0^{pab}1^p ko 1 \leq b \leq p.

Niha, rêzê bifikirin xy^2z = 0^a0^{2b}0^{pab}1^p = 0^{p+b}1^p. Hejmara 0yan e p + b, ku jê mezintir e p, dema ku hejmara 1an dimîne p. Ji ber vê yekê, xy^2z \notin U ji ber ku hejmarên 0 û 1an ne wek hev in. Ev nakokî nîşan dide ku texmîna ku U birêkûpêk e derew e. Ji ber vê yekê, U = \{0^n1^n \mid n \geq 0\} ne zimanekî asayî ye.

Zimanên Bê-Context û Otomata Pushdown

Ziman U = \{0^n1^n \mid n \geq 0\} Lêbelê, zimanek bê-conteks (CFL) ye. Zimanên bê naverokê ji hêla otomatên pushdown (PDA) ve têne nas kirin, ku ji otomatên dawîn bi hêztir in ji ber ku ew dikarin stekê bikar bînin da ku hejmareke bêsînor agahiyê hilînin. Ev bîra zêde rê dide PDA-yan ku di ziman de hejmara 0 û 1an bişopînin U.

PDA ji bo U = \{0^n1^n \mid n \geq 0\} wiha tevdigere:
1. Ew di rewşek destpêkê de dest pê dike û 0-an ji têketinê dixwîne, her 0-ê dixe stikê.
2. Piştî xwendina yekem 1, ew derbasî rewşek nû dibe û ji bo her 0 xwendina ji têketinê dest bi derxistina 1-an ji stikê dike.
3. Ger steck vala be dema ku têketin biqede, PDA têketinê qebûl dike, nîşan dide ku hejmara 0yan bi hejmara 1an re li hev dike.

Ev mekanîzmaya bikaranîna stackê ku jimara 0 û 1-an li hev dike, kapasîteya PDA-yan destnîşan dike ku zimanên ku ne birêkûpêk in lê ji çarçoweyê bêpar in nas bikin.

Nimûne û Encamên Zêdetir

Mînaka rêzê bifikirin s = 000111 ji zimên U. PDA dê vê rêzê bi pêvekirina her 0-ê li ser stêkê gava ku ew wan dixwîne pêvajoyê bike. Piştî xwendina sê 0-an, stêk dê sê sembolan bihewîne, ku her yek 0-yê temsîl dike. Dema ku PDA 1-yên paşerojê dixwîne, ji bo her 1-an sembolek ji stikê derdixe. Dema ku têketin bi tevahî were xwendin, stêk vala ye, ev nîşan dide ku input tê qebûl kirin.

Berevajî vê, otomatek bêdawî dê nikaribe hejmara 0 û 1-an bişopîne, ji ber ku ew mekanîzmaya stakê tune ye. Bêyî şiyana hilanîn û vegerandina hejmareke bêsînor ji sembolan, otomatek bêdawî nikare piştrast bike ku hejmara 0-an bi hejmara 1-an re ye, û dibe sedem ku nekare wî zimanî nas bike. U.

Cûdahiya di navbera zimanên birêkûpêk û yên bê kontekst de di zanistiya kompîturê ya teorîkî de girîng e û di warên wekî sêwirana zimanê bernamekirinê û parskirinê de bandorên pratîkî hene. Rêzimanên bê-contekst, ku zimanên bê kontekst diafirînin, di pênaseya hevoksaziya zimanên bernamesaziyê de bi berfirehî têne bikar anîn. Qabiliyeta naskirina zimanên bê-conteks bi karîgerî bi karanîna PDA-yan, pêşkeftina parserên ku ji berhevkar û wergêran re bingehîn in bingeh digire.

Ne-rêkûpêkî ya U = \{0^n1^n \mid n \geq 0\} tixûbên otomatên bêdawî destnîşan dike û hewcedariya modelên hesabker ên bihêztir ên mîna otomatên pushdown ji bo naskirina çînek berfireh a zimanan ronî dike. Ev ciyawazî ne tenê teorîk e, lê di sêwirandin û pêkanîna pratîkî ya zimanên bernamekirinê û amûrên ku wan pêvajo dikin de bandorên kûr hene.

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: , , , , ,