Pushdown Automata (PDA) нь тооцооллын янз бүрийн талыг судлахад онолын компьютерийн шинжлэх ухаанд ашиглагддаг тооцооллын загвар юм. PDA нь тооцооллын нарийн төвөгтэй байдлын онолын хүрээнд онцгой хамааралтай бөгөөд янз бүрийн төрлийн асуудлыг шийдвэрлэхэд шаардагдах тооцооллын нөөцийг ойлгох үндсэн хэрэгсэл болдог. Үүнтэй холбогдуулан PDA нь палиндром мөрийн хэлийг илрүүлж чадах эсэх нь энэхүү тооцооллын загварын боломж, хязгаарлалтыг судлах болно.
Энэ асуултыг шийдвэрлэхийн тулд эхлээд палиндром мөр гэж юу болохыг олж мэдэх хэрэгтэй. Палиндром гэдэг нь ижил урагшаа, хойшоо уншдаг тэмдэгтүүдийн дараалал юм. Жишээлбэл, "радар" ба "түвшин" нь хоёулаа палиндром мөрүүдийн жишээ юм. Палиндромын хэлхээний хэл нь өгөгдсөн цагаан толгойн дээрх бүх боломжит палиндромуудаас бүрдэнэ. Одоо байгаа ажил бол PDA нь өгөгдсөн оролтын мөр нь палиндром мөн эсэхийг таньж чадах эсэхийг тодорхойлох явдал юм.
PDA-ийн хувьд палиндром мөрийг таних чадвар нь PDA-ийн тооцоолох чадвар болон палиндром мөрүүдийн онцлог шинж чанараас хамаардаг. PDA нь оролтын тэмдэгтүүдийг уншихаас гадна стекийг удирдах чадвартай бөгөөд энэ нь хязгаарлагдмал автоматтай харьцуулахад илүү их тооцоолох хүчийг өгдөг. Энэхүү нэмэлт чадвар нь PDA-д зөвхөн хязгаарлагдмал автоматаар танигдахгүй зарим төрлийн хэлийг таних боломжийг олгодог.
Палиндромын хэлхээний тухайд PDA-ийн ашиглаж болох гол шинж чанар нь палиндромын бүтэц нь тэгш хэмтэй байдаг явдал юм. Энэхүү тэгш хэм нь PDA-д оролтын мөрийн эхэн ба төгсгөлд байгаа тэмдэгтүүдийг харьцуулах боломжийг олгодог бөгөөд тэдгээрийн хоорондох тэмдэгтүүдийг хянахын тулд стекийг ашиглана. Тэмдэгтүүдийг хадгалах, авахын тулд стекийг зохих ёсоор ашигласнаар PDA нь өгөгдсөн оролтын мөр нь палиндром эсэхийг шалгаж чадна.
PDA ашиглан палиндром мөрийг илрүүлэх үйл явц нь тэмдэгтүүдийг харьцуулахын тулд стекийг ашиглахын зэрэгцээ оролтын мөрийг хоёр төгсгөлөөс нэгэн зэрэг гатлах явдал юм. Алхам бүрт PDA нь оролтын мөрний хоёр төгсгөлийн тэмдэгтүүдийг уншиж, тэдгээр нь таарч байгаа эсэхийг харьцуулж чаддаг. Хэрэв тохиромжгүй байдал илэрсэн эсвэл мөрийг бүхэлд нь боловсруулж, стек хоосон байвал PDA нь оролтын мөрийг палиндром биш гэж үгүйсгэж болно. Нөгөө талаас, хэрэв PDA оролтын мөрийг бүхэлд нь амжилттай боловсруулж, стек хоосон байвал оролтын мөрийг палиндром гэж хүлээн авна.
PDA нь тэмдэгтүүдийг тэгш хэмтэй харьцуулахын тулд стек дээр суурилсан чадвараа ашиглан палиндром мөрийн хэлийг илрүүлж чаддаг. Энэ үйл явц нь палиндром гэх мэт бүтцийн онцлог шинж чанартай зарим төрлийн хэлийг танихад PDA-ийн тооцоолох чадварыг харуулдаг.
Сүүлийн үеийн бусад асуулт, хариулт EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс:
- Хомскийн дүрмийн хэвийн хэлбэрийг үргэлж шийдвэрлэх боломжтой юу?
- Тогтмол илэрхийлэлийг рекурс ашиглан тодорхойлж болох уу?
- OR-ийг FSM гэж хэрхэн төлөөлөх вэ?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
- P ангиллын баталгаажуулагч олон гишүүнт мөн үү?
- Галт ханын тохиргоон дахь төлөвийн шилжилт болон үйлдлүүдийг илэрхийлэхэд тодорхой бус төгсгөлийн автомат машиныг (NFA) ашиглаж болох уу?
- Олон соронзон хальсны TN-д гурван соронзон хальс ашиглах нь нэг соронзон хальсны хугацаа t2 (дөрвөлжин) эсвэл t3 (шоо) -тай тэнцэх үү? Өөрөөр хэлбэл, цаг хугацааны нарийн төвөгтэй байдал нь соронзон хальсны тоотой шууд холбоотой юу?
- Тогтмол цэгийн тодорхойлолт дахь утга нь функцийн давтан хэрэглээний хязгаар бол бид үүнийг тогтмол цэг гэж нэрлэж болох уу? Үзүүлсэн жишээн дээр 4->4-ийн оронд 4->3.9, 3.9->3.99, 3.99->3.999 байвал … 4 нь тогтмол цэг хэвээрээ байх уу?
- Хэрэв бид шийдвэрлэх боломжтой хэлийг дүрсэлсэн хоёр TM-тэй бол тэнцэх асуултыг шийдвэрлэх боломжгүй хэвээр байна уу?
- Соронзон хальсны эхлэлийг илрүүлэх тохиолдолд баруун тийш шилжихийн оронд шинэ соронзон хальсыг T1=$T ашиглан эхлүүлж болох уу?