Ердийн хэлний хүрээнд шийдвэрлэх боломжтой асуулт гэж юу гэсэн үг вэ?
Шийдвэрлэх боломжтой асуулт нь ердийн хэлнүүдийн хувьд баталгаатай зөв гарц бүхий алгоритмаар хариулж болох асуултыг хэлнэ. Өөрөөр хэлбэл, энэ нь тодорхой хугацааны дотор хариултыг тодорхойлох тооцооллын журамтай асуулт юм.
Шийдвэрлэх асуултын тухай ойлголтыг энгийн хэлний хүрээнд ойлгохын тулд эхлээд ердийн хэлний талаар тодорхой ойлголттой байх нь чухал юм. Тогтмол хэлүүд нь компьютерийн шинжлэх ухааны үндсэн ойлголт бөгөөд хязгаарлагдмал автомат эсвэл тогтмол хэллэгээр танигдах хэв маяг, мөрийн багцыг тодорхойлоход хэрэглэгддэг.
Шийдвэрлэх чадвар гэдэг нь Тьюрингийн машин эсвэл бусад түүнтэй адилтгах тооцооллын загвараар үр дүнтэй танигдах хэлний ангиллыг тодорхойлдог шинж чанар юм. Аливаа оролтын мөрийг өгөгдсөн мөр нь тухайн хэлэнд хамаарах эсэхийг тодорхойлох алгоритм байгаа бол хэлийг шийдэх боломжтой.
Энгийн хэлнүүдийн хувьд шийдвэрлэх боломжтой асуултыг дараах байдлаар томъёолж болно: Энгийн хэл L болон w тэмдэгт өгөгдсөн бол wa нь L хэлний гишүүн мөн үү? Энэ асуултад L хэлийг таних хязгаарлагдмал автомат машин байгуулж, w оролтын мөрөнд автоматыг дуурайснаар хариулж болно. Хэрэв автомат w-г хүлээн авбал асуултын хариулт "тийм" болно; Үгүй бол хариулт нь "үгүй".
Жишээлбэл, бүх хоёртын мөрийн багцыг илэрхийлдэг L = {0, 1}* энгийн хэлийг авч үзье. w = 101010 тэмдэгт мөрийг өгвөл шийдвэрлэх боломжтой асуулт нь: wa L гишүүн мөн үү? Энэ асуултад хариулахын тулд бид L хэлийг таньдаг хязгаарлагдмал автомат машин бүтээж, w оролтын мөрөнд автоматыг дуурайж болно. Хэрэв автомат оролтын мөрийг бүхэлд нь боловсруулсны дараа хүлээн авах төлөвт хүрсэн бол "тийм" гэж хариулна; Үгүй бол хариулт нь "үгүй". Энэ тохиолдолд автомат машин хүлээн авах төлөвт хүрэх тул "тийм" гэж хариулна.
Шийдвэрлэх чадвар нь ердийн хэлнүүдийн хувьд хүссэн шинж чанар юм, учир нь энэ нь аливаа ердийн хэлний гишүүнчлэлийн асуудлыг шийдэж чадах алгоритм байгаа эсэхийг баталгаажуулдаг. Энэ өмч нь компьютерийн шинжлэх ухааны янз бүрийн салбарт, тэр дундаа кибер аюулгүй байдалд чухал ач холбогдолтой бөгөөд халдлагыг илрүүлэх системийн загварыг тодорхойлох эсвэл хандалтын хяналтын бодлогыг тодорхойлоход ердийн хэлийг ихэвчлэн ашигладаг.
Энгийн хэлний контекст дэх шийдвэрлэх боломжтой асуулт гэдэг нь баталгаатай зөв гарц бүхий алгоритмаар хариулж болох асуултыг хэлнэ. Энэ нь тодорхой хугацааны дотор хариултыг тодорхойлох тооцооллын журамтай асуулт юм. Шийдвэрлэх чадвар нь аливаа ердийн хэлний гишүүнчлэлийн асуудлыг шийдэж чадах алгоритм байгаа эсэхийг баталгаажуулдаг тул ердийн хэлнүүдийн хувьд хүсүүштэй шинж чанар юм.
Сүүлийн үеийн бусад асуулт, хариулт EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс:
- Детерминистик бус PDA-уудыг авч үзвэл мужуудын суперпозиция нь тодорхойлолтоор боломжтой юм. Гэсэн хэдий ч детерминистик бус PDA нь зөвхөн нэг стектэй байдаг бөгөөд энэ нь нэгэн зэрэг олон төлөвт байж болохгүй. Энэ яаж боломжтой вэ?
- Сүлжээний урсгалд дүн шинжилгээ хийх, аюулгүй байдлын болзошгүй зөрчлийг илтгэх хэв маягийг тодорхойлоход ашигладаг PDA-ийн жишээ юу вэ?
- Нэг хэл нөгөө хэлээсээ илүү хүчтэй гэдэг нь юу гэсэн үг вэ?
- Контекст мэдрэмтгий хэлүүдийг Тьюрингийн машин таних боломжтой юу?
- U = 0^n1^n (n>=0) хэл яагаад тогтмол бус байна вэ?
- Тэгш тооны '1' тэмдэгт бүхий хоёртын мөрийг таних FSM-г хэрхэн тодорхойлж, 1011 оролтын мөрийг боловсруулахад юу болдгийг харуулах вэ?
- Нотертерминизм нь шилжилтийн функцэд хэрхэн нөлөөлдөг вэ?
- Энгийн хэлүүд нь хязгаарлагдмал төрийн машинуудтай тэнцэх үү?
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- Алгоритмын хувьд тооцоолж болох асуудал нь Тьюрингийн машинаар тооцоолж болох асуудал мөн үү?