Pushdown Automata (PDA) یو کمپیوټري ماډل دی چې د کمپیوټر ساینس په تیوري کې کارول کیږي ترڅو د کمپیوټر مختلف اړخونه مطالعه کړي. PDAs په ځانګړي ډول د کمپیوټري پیچلتیا تیوري په شرایطو کې اړونده دي، چیرې چې دوی د مختلف ډوله ستونزو حل کولو لپاره اړین کمپیوټري سرچینو درک کولو لپاره د بنسټیز وسیلې په توګه کار کوي. په دې اړه، دا پوښتنه چې ایا PDA کولی شي د پالینډروم تار ژبه کشف کړي د دې کمپیوټري ماډل وړتیاوو او محدودیتونو ته اشاره کوي.
د دې پوښتنې د حل کولو لپاره، موږ باید لومړی دا معلومه کړو چې د پالینډروم تار څه شی دی. پالینډروم د کرکټرونو لړۍ ده چې ورته مخکینۍ او شاته لوستل کیږي. د مثال په توګه، "رادار" او "سطح" دواړه د پالینډروم تارونو مثالونه دي. د پالینډروم تارونو ژبه د یو ټاکل شوي الفبا په اوږدو کې د ټولو ممکنه پالینډرومونو څخه جوړه ده. په لاس کې دنده دا ده چې دا معلومه کړي چې ایا PDA کولی شي پیژني یا معلومه کړي چې ایا ورکړل شوی ان پټ تار یو پالینډروم دی.
د PDAs په شرایطو کې، د پالینډروم تار پیژندلو وړتیا د PDA کمپیوټري ځواک او د پالینډروم تارونو ځانګړو ځانګړتیاو پورې اړه لري. PDAs د ان پټ سمبولونو لوستلو سربیره د سټیک د مینځلو وړتیا لري ، کوم چې دوی ته د محدود اتوماتیک په پرتله ډیر کمپیوټري ځواک ورکوي. دا اضافي وړتیا PDAs ته اجازه ورکوي چې د ژبې ځینې ډولونه وپیژني چې یوازې د محدود اتوماتیک لخوا نشي پیژندل کیدی.
کله چې دا د پالینډروم تارونو ته راځي ، کلیدي ملکیت چې د PDA لخوا کارول کیدی شي دا حقیقت دی چې د پالینډروم جوړښت سمیټریک دی. دا همغږي PDA ته اجازه ورکوي چې د ان پټ سټینګ په پیل او پای کې حروف پرتله کړي پداسې حال کې چې د هغې سټیک کاروي ترڅو په مینځ کې د کرکټرونو تعقیب وساتي. د کرکټرونو ذخیره کولو او ترلاسه کولو لپاره د دې سټیک په مناسبه توګه کارولو سره ، PDA کولی شي تصدیق کړي چې ایا ورکړل شوی ان پټ سټرینګ پیلینډروم دی.
د PDA په کارولو سره د پالینډروم تارونو کشف کولو پروسه په عموم ډول د دواړو سرونو څخه په ورته وخت کې د ان پټ تار تیریدل شامل دي پداسې حال کې چې د حروف پرتله کولو لپاره د سټیک کارول شامل دي. په هر ګام کې، PDA کولی شي د ان پټ سټینګ دواړو پایونو څخه حروف ولولي او پرتله یې کړي ترڅو ډاډ ترلاسه کړي چې دوی سره سمون لري. که یو بې اتفاقي وموندل شي یا که ټول تار پروسس شوی وي او سټیک خالي وي ، PDA کولی شي د ان پټ سټینګ د پیلینډروم نه وي په توګه رد کړي. له بلې خوا، که PDA په بریالیتوب سره ټول ان پټ تار پروسس کړي او سټیک خالي وي، د ان پټ سټینګ د پالینډروم په توګه منل کیږي.
A PDA په حقیقت کې کولی شي د پیلینډوم تارونو ژبه کشف کړي د دې سټیک پراساس وړتیاو په کارولو سره په سمیټریک ډول د کرکټرونو پرتله کولو لپاره. دا پروسه د PDAs کمپیوټري ځواک ښیې چې د ځانګړو ډولونو ژبو پیژندلو کې چې ځانګړي ساختماني ملکیتونه ښیې لکه پالینډرومونه.
په اړه نورې وروستۍ پوښتنې او ځوابونه EITC/IS/CCTF د کمپیوټري پیچلتیا تیوري اساسات:
- ایا د چومسکي ګرامر نورمال بڼه تل د پریکړې وړ ده؟
- ایا یو منظم بیان د تکرار په کارولو سره تعریف کیدی شي؟
- څنګه د FSM په توګه یا استازیتوب وکړو؟
- ایا د NP تعریف د ټولګي په توګه د پریکړو ستونزو د ټولګي په توګه د پولینیمیل وخت تصدیق کونکو سره تضاد شتون لري او دا حقیقت چې په ټولګي P کې ستونزې هم د پولینومیل وخت تصدیق کونکي لري؟
- ایا د ټولګي P پولینومیل لپاره تصدیق کونکی دی؟
- ایا د غیر متمرکز فینایټ اتومات (NFA) کارول کیدی شي د فایروال ترتیب کې د دولت لیږدونو او کړنو نمایندګي لپاره؟
- ایا په ملټي ټیپ TN کې د دریو ټیپونو کارول د واحد ټیپ وخت t2 (مربع) یا t3 (مکعب) سره مساوي دي؟ په بل عبارت ایا د وخت پیچلتیا مستقیم د ټیپونو شمیر سره تړاو لري؟
- که د ثابت ټکي په تعریف کې ارزښت د فنکشن د تکرار پلي کیدو محدودیت وي ایا موږ کولی شو دا لاهم ثابت ټکی ووایو؟ په مثال کې ښودل شوي که د 4->4 پرځای موږ 4->3.9، 3.9->3.99، 3.99->3.999، … 4 اوس هم ثابت ټکی دی؟
- که موږ دوه TMs ولرو چې د پریکړې وړ ژبه بیانوي ایا د مساوي پوښتنه لاهم د نه منلو وړ ده؟
- د ټیپ د پیل موندلو په حالت کې، ایا موږ کولی شو د نوي ټیپ په کارولو سره پیل وکړو T1=$T د دې پرځای چې ښي خوا ته واړوو؟
نورې پوښتنې او ځوابونه په EITC/IS/CCTF کې وګورئ د کمپیوټري پیچلتیا تیوري اساسات