Pushdown Automata (PDA) modelek hesabkerî ye ku di zanistiya komputerê ya teorîkî de tê bikar anîn da ku aliyên cûda yên hesabkirinê lêkolîn bike. PDA bi taybetî di çarçoveya teoriya tevliheviya hesabkirinê de têkildar in, ku ew wekî amûrek bingehîn ji bo têgihîştina çavkaniyên hesabker ên ku ji bo çareserkirina cûreyên cûda yên pirsgirêkan hewce ne re xizmet dikin. Di vî warî de, pirsa gelo PDA dikare zimanê xêzek palindromê tespît bike, di nav kapasîteyên û tixûbên vê modela hesabker de vedigere.
Ji bo ku em vê pirsê çareser bikin, pêşî hewce ye ku em destnîşan bikin ka stringek palindrome çi ye. Palindrom rêzek karakteran e ku heman pêş û paş dixwîne. Mînakî, "radar" û "asta" herdu jî mînakên têlên palindromê ne. Zimanê rêzikên palindromê ji hemî palindromên gengaz ên li ser alfabeyek diyarkirî pêk tê. Peywira li ber dest ev e ku meriv diyar bike ka PDA dikare nas bike an tesbît bike ka rêzika têketinê ya diyar palindrom e.
Di çarçoweya PDA-yan de, şiyana naskirina rêzek palindromê bi hêza hesabker a PDA û taybetmendiyên taybetî yên rêzikên palindromê ve girêdayî ye. PDA ji bilî xwendina sembolên têketinê xwedan şiyana manîpulekirina stekê ye, ku li gorî otomatên bêdawî bêtir hêza hesabkirinê dide wan. Vê kapasîteya zêde rê dide PDA-yan ku hin cûreyên zimanan nas bikin ku tenê ji hêla otomatên bêdawî ve nayên naskirin.
Dema ku dor tê ser rêzikên palindromê, taybetmendiya sereke ya ku ji hêla PDA-yê ve dikare were bikar anîn ev rastiyek e ku avahiya palindromê sîmetrîk e. Ev simetrî destûrê dide PDA-yê ku karakterên li destpêk û dawiya rêzika têketinê bide ber hev dema ku stika xwe bikar tîne da ku tîpên di navberê de bişopîne. Bi karanîna guncan a stûna xwe ji bo hilanîn û wergirtina karakteran, PDA dikare verast bike ka rêzika têketinê ya hatî dayîn palindrom e.
Pêvajoya tesbîtkirina rêzikên palindromê bi karanîna PDA-yê bi gelemperî derbaskirina xêza têketinê ji her du seriyan bi hevdemî vedihewîne dema ku stikê ji bo berhevdana karakteran bikar tîne. Di her gavê de, PDA dikare tîpan ji herdu dawiya rêzika têketinê bixwîne û wan bide ber hev da ku pê ewle bibe ku ew li hev dikin. Ger neliheviyek were tespît kirin an heke tevahiya rêzik were pêvajo kirin û stûn vala be, PDA dikare rêzika têketinê red bike ku ne palindrom e. Ji hêla din ve, heke PDA bi serfirazî tevahiya rêzika têketinê bişopîne û stûn vala be, rêzika têketinê wekî palindromek tê pejirandin.
PDA bi rastî dikare zimanê rêzikên palindromê bi karanîna kapasîteyên xwe yên li ser stack-ê destnîşan bike da ku karakteran bi rengek sîmetrîk bide ber hev. Ev pêvajo hêza hesabker a PDA-yan di naskirina hin cûreyên zimanên ku taybetmendiyên avahîsaziyê yên taybetî nîşan didin, mîna palindroman, nîşan dide.
Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:
- Rêzimana Chomsky ya normal her gav biryardar e?
- Ma bi karanîna vegerê birêkûpêkek birêkûpêk dikare were destnîşankirin?
- Meriv çawa OR wekî FSM temsîl dike?
- Ma nakokî di navbera pênasekirina NP-ê de wekî çînek pirsgirêkên biryarê yên bi verastkerên polînomî-dem-ê re û rastiya ku pirsgirêkên di pola P-yê de verastkerên dema pirnomî jî hene?
- Ma verastker ji bo pola P polînomî ye?
- Ma dikare Otomatona Dawî ya Nedeterminîstîk (NFA) were bikar anîn da ku veguheztin û kiryarên dewletê di veavakirina dîwarê agir de temsîl bike?
- Bikaranîna sê kasetan di TN-ya pirtengî de bi dema kasêta yekane t2 (çargoşe) an t3 (kube) re wekhev e? Bi gotineke din gelo tevliheviya demê rasterast bi hejmara kasetan re têkildar e?
- Ger nirxa di pênaseya xala sabît de sînorê sepana dubare ya fonksiyonê be, gelo em dikarin jê re hîn jî wekî xalek sabît bi nav bikin? Di mînaka nîşandayî de heke li şûna 4->4-ê me 4->3.9, 3.9->3.99, 3.99->3.999 hebe, ... ma 4 dîsa jî xala sabît e?
- Ger du TM-yên me hene ku zimanek biryardar diyar dikin, gelo pirsa wekheviyê hîn jî nayê biryar?
- Di rewşa tesbîtkirina destpêka kasêtê de, gelo em dikarin li şûna ku ber bi rastê ve biçin, kasetek nû T1=$T bikar bînin?
Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin