Рекурсив тоологдох хэл гэж нэрлэгддэг 0 төрлийн хэл нь тооцооллын нарийн төвөгтэй байдлын хувьд бусад төрлийн хэлнээс юугаараа ялгаатай вэ?
Төрөл 0 хэл, өөрөөр хэлбэл рекурсив тоологдох хэлүүд нь бусад төрлийн хэлүүдээс тооцооллын нарийн төвөгтэй байдлын хувьд хэд хэдэн зүйлээр ялгаатай байдаг. Эдгээр ялгааг ойлгохын тулд Чомскийн шатлал болон контекст мэдрэмтгий хэлнүүдийн талаар сайн ойлголттой байх нь чухал юм.
Хомскийн шатлал нь албан ёсны хэлийг тэдгээрийг үүсгэсэн дүрмийн төрлөөс хамааран ангилдаг. Энэ нь 3-р төрөл (ердийн хэлүүд), 2-р төрөл (контекстгүй хэлүүд), 1-р төрөл (контекст мэдрэмтгий хэлүүд), төрөл 0 (рекурсив тоологдох хэл) гэсэн дөрвөн түвшингээс бүрдэнэ. Шатлалын түвшин бүр өөр өөр түвшний тооцооллын нарийн төвөгтэй байдлыг илэрхийлдэг.
Төрөл 0 хэл буюу рекурсив тоолох боломжтой хэл нь тооцооллын нарийн төвөгтэй байдлын хувьд хамгийн хүчирхэг хэл юм. Тэдгээрийг Тьюрингийн машинууд таних боломжтой бөгөөд энэ нь ямар ч алгоритмыг дуурайх чадвартай хийсвэр тооцооллын төхөөрөмж юм. Тюринг машин байгаа бол тухайн хэл дээрх ямар ч мөрийг зогсоож, хүлээж авах боловч тухайн хэлэнд байхгүй мөртүүдийн хувьд тодорхойгүй хугацаагаар давтагдах боломжтой бол хэлийг рекурсив тоолж болно.
Үүний эсрэгээр, 3-р төрлийн хэлийг (ердийн хэл) хязгаарлагдмал автоматаар таних боломжтой бөгөөд энэ нь илүү хялбар тооцоолох төхөөрөмж юм. Энгийн хэлүүд нь шугаман хугацаанд танигдах боломжтой тул дөрвөн төрлөөс хамгийн бага тооцоолох нарийн төвөгтэй хэлтэй байдаг.
2-р төрлийн хэл (контекстгүй хэлүүд) нь ердийн хэлээс илүү төвөгтэй боловч рекурсив тоолох боломжтой хэлнүүдээс бага төвөгтэй байдаг. Тэдгээрийг контекстийг хянах стек бүхий түлхэх автоматаар таних боломжтой. Контекстгүй хэлийг олон гишүүнт цаг хугацаанд таньж болно.
1-р төрлийн хэлүүд (контекст мэдрэмтгий хэл) нь контекстгүй хэлнүүдээс илүү төвөгтэй боловч рекурсив тоолох боломжтой хэлнүүдээс бага төвөгтэй байдаг. Тэдгээрийг шугаман хязгаарлагдмал автоматаар таних боломжтой бөгөөд тэдгээр нь оролтын хэмжээнээс хамааран өсөх хязгаарлагдмал санах ойтой байдаг. Контекст мэдрэмтгий хэлийг детерминистик бус олон гишүүнт цаг хугацаанд таньж болно.
0 төрлийн хэл болон бусад төрлүүдийн хоорондох гол ялгаа нь тэдний тооцоолох хүчин чадалд оршдог. Төрөл 0 хэл нь Тьюрингийн машинаар таних ямар ч хэлийг таньж чаддаг бөгөөд энэ нь тэдгээрийг хамгийн илэрхийлэлтэй, хүчирхэг болгодог. Гэсэн хэдий ч энэ хүч нь тооцооллын нарийн төвөгтэй байдлыг нэмэгдүүлэх зардлаар ирдэг. Тьюрингийн машин тухайн хэлэнд байхгүй мөртүүдийн хувьд тодорхойгүй хугацаагаар давталт хийж болох тул рекурсив тоолж болох хэлийг танихад хязгааргүй хугацаа шаардагдана.
Үүний эсрэгээр, ердийн, контекстгүй, контекст мэдрэмтгий хэлүүд нь тооцоолох чадвар илүү хязгаарлагдмал боловч тэдгээрийг таних алгоритмууд нь нарийн төвөгтэй байдал багатай байдаг. Энгийн хэлийг шугаман цаг, контекстгүй хэлийг олон гишүүнт цаг, контекст мэдрэмтгий хэлийг детерминистик бус олон гишүүнт цаг хугацаанд таньж болно.
Эдгээр ялгааг харуулахын тулд жишээг авч үзье. Бидэнд "a^nb^nc^n" хэлбэрийн бүх мөрүүдээс бүрдэх L хэл байна гэж бодъё, энд n нь эерэг бүхэл тоо юм. Энэ хэл нь хязгаарлагдмал автоматаар хийх боломжгүй 'a, 'b', 'c'-ийн тоог тоолохыг шаарддаг тул тогтмол биш юм. Гэсэн хэдий ч энэ нь контекстгүй дүрмээр танигдах боломжтой бөгөөд энэ нь контекстгүй хэл юм. Энэ хэлийг таних алгоритм нь олон гишүүнт нарийн төвөгтэй байдаг. Нөгөөтэйгүүр, таних үйл явцыг дуурайж чадах Тьюрингийн машин байдаг тул L хэлийг мөн рекурсив тоолох боломжтой. Гэсэн хэдий ч, энэ таних алгоритм нь илүү нарийн төвөгтэй бөгөөд хэл дээр биш мөртүүдийг зогсоохгүй байж болно.
Төрөл 0 хэл буюу рекурсив тоолох боломжтой хэл нь тооцооллын нарийн төвөгтэй байдлын хувьд бусад төрлийн хэлнээс ялгаатай. Эдгээр нь тооцооллын илэрхийлэлийн хувьд хамгийн хүчирхэг боловч хамгийн нарийн төвөгтэй байдаг. Тогтмол, контекстгүй, контекст мэдрэмтгий хэлүүд нь тооцооллын төвөгтэй байдал багатай боловч илэрхийлэл багатай байдаг. Эдгээр ялгааг ойлгох нь алгоритмын нарийн төвөгтэй байдал болон өөр өөр төрлийн хэлний аюулгүй байдлын үр нөлөөг шинжлэхэд тусалдаг тул кибер аюулгүй байдлын салбарт чухал ач холбогдолтой юм.
Сүүлийн үеийн бусад асуулт, хариулт Хомскийн шатлал ба агуулгын мэдрэмжтэй хэл:
- Type-0-ийг таних одоогийн аргууд байдаг уу? Бид квант компьютерууд үүнийг хэрэгжүүлэх боломжтой гэж найдаж байна уу?
- Нэг, хоёр, гурвын тэнцүү тооны мөрүүдээс бүрдэх хэлний контекст мэдрэмтгий дүрмийг зохиох үйл явцыг тайлбарла.
- Контекст мэдрэмтгий хэлний жишээг өгч, түүнийг контекст мэдрэмтгий дүрмээр хэрхэн танихыг тайлбарла.
- Контекстээс ангид хэл ба контекст мэдрэмтгий хэл хоёрын ялгааг тэдгээрийн үүсэх дүрмийн дагуу тайлбарла.
- Хэлний Чомскийн шатлал гэж юу вэ, түүнийг үүсгэх чадвараар нь албан ёсны дүрмийг хэрхэн ангилдаг вэ?