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