Хэлний Чомскийн шатлал гэж юу вэ, түүнийг үүсгэх чадвараар нь албан ёсны дүрмийг хэрхэн ангилдаг вэ?
Хомскийн хэлнүүдийн шатлал нь албан ёсны дүрмүүдийг үүсгэх чадвараар нь ангилдаг ангиллын систем юм. Үүнийг 1950-иад онд нэрт хэл шинжлэлийн эрдэмтэн, компьютер судлаач Ноам Хомски дэвшүүлсэн. Шатлал нь дөрвөн түвшнээс бүрдэх бөгөөд тус бүр нь албан ёсны хэлний өөр өөр ангиллыг төлөөлдөг. Эдгээр түвшнийг Type-3 (Regular), Type-2 (Context-Free), Type-1 (Context-Sensitive), Type-0 (Unlimited) гэж нэрлэдэг.
Шатлалын хамгийн доод түвшинд бид ердийн хэл гэж нэрлэгддэг 3-р төрлийн хэлтэй. Эдгээр хэлийг детерминист ба детерминист бус төгсгөлөг автоматууд гэх мэт хязгаарлагдмал автоматаар таньж болно. Тогтмол хэл нь тогтмол хэллэг, тогтмол дүрмээр тодорхойлогддог. Тогтмол хэллэгүүд нь мөрийн хэв маягийг дүрсэлсэн алгебрийн хэллэгүүд байдаг бол ердийн дүрэм нь ердийн хэл дээр мөр үүсгэдэг үйлдвэрлэлийн дүрмүүдээс бүрддэг. Энгийн хэлний жишээ бол тэгш тоо 0-тэй бүх хоёртын мөрийн хэл гэх мэт өгөгдсөн тогтмол илэрхийлэлтэй тохирох бүх мөрүүдийн багц юм.
Шатлалыг дээшлүүлснээр бид Context-Free хэл гэж нэрлэгддэг 2-р төрлийн хэлтэй тулгардаг. Эдгээр хэлийг түлхэх автоматаар таних боломжтой бөгөөд энэ нь стекээр нэмэгдүүлсэн хязгаарлагдмал автоматууд юм. Контекстгүй хэлүүдийг контекстгүй хэл дээр мөр үүсгэдэг үйлдвэрлэлийн дүрмүүдээс бүрдэх контекстгүй дүрмээр тайлбарладаг. Контекстгүй дүрмүүд нь терминалын бус тэмдэгтүүд, терминалын тэмдэгтүүд ба үйлдвэрлэлийн дүрмүүдтэй байдаг бөгөөд тэдгээр нь терминал бусуудыг тэмдэгтүүдийн дараалалаар хэрхэн сольж болохыг тодорхойлдог. Контекстгүй хэлний жишээ бол хашилтыг тэнцвэржүүлж, операторуудыг зөв ашигласан бүх зөв хэлбэртэй арифметик илэрхийллийн багц юм.
Шатлалын дараагийн түвшин бол Контекст мэдрэмтгий хэл гэж нэрлэгддэг 1-р төрлийн хэл юм. Эдгээр хэлийг шугаман хязгаарлагдмал автоматаар таних боломжтой бөгөөд эдгээр нь хоёр чиглэлд шилжих боломжтой соронзон хальстай төгсгөлтэй автоматууд юм. Контекст мэдрэмтгий хэлүүдийг контекст мэдрэмтгий хэл дээр мөр үүсгэдэг үйлдвэрлэлийн дүрмүүдээс бүрдэх контекст мэдрэмтгий дүрмээр тайлбарладаг. Контекст мэдрэмтгий дүрмүүд нь үйлдвэрлэлийн дүрмийн баруун талын урт нь зүүн талын уртаас богино байж болохгүй гэсэн нэмэлт хязгаарлалттай байдаг. Контекст мэдрэмтгий хэлний жишээ бол бүх палиндромуудын багц бөгөөд мөр нь урагш болон хойшоо адилхан уншдаг.
Эцэст нь, шатлалын дээд хэсэгт бид Хязгааргүй хэл гэж нэрлэгддэг Type-0 хэлүүдтэй. Эдгээр хэлийг Тьюрингийн машинууд таних боломжтой бөгөөд энэ нь ямар ч компьютерийн алгоритмыг дуурайх чадвартай хийсвэр тооцооллын төхөөрөмж юм. Хязгаарлагдаагүй хэлийг үйлдвэрлэлийн дүрэмд хязгаарлалт тавьдаггүй, хязгаарлалтгүй дүрмээр тайлбарладаг. Хязгаарлагдаагүй хэлний жишээ нь бүх тооцоолж болох хэлүүдийг багтаасан бүх рекурсив тоолж болох хэлний багц юм.
Хомскийн хэлний шатлал нь албан ёсны дүрмүүдийг үүсгэх чадварт нь үндэслэн ангилах системчилсэн тогтолцоог бүрдүүлдэг. Энэ нь хамгийн бага хүчин чадалтай ердийн хэлээр эхэлж, контекстээс ангид, контекст мэдрэмтгий, хязгаарлалтгүй хэл рүү шилжиж, улам бүр хүчирхэг болж байна. Энэхүү шатлал нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн ойлголт бөгөөд албан ёсны хэл, автоматыг судлахад чухал ач холбогдолтой юм.
Сүүлийн үеийн бусад асуулт, хариулт Хомскийн шатлал ба агуулгын мэдрэмжтэй хэл:
- Нэг хэл нөгөө хэлээсээ илүү хүчтэй гэдэг нь юу гэсэн үг вэ?
- Type-0-ийг таних одоогийн аргууд байдаг уу? Бид квант компьютерууд үүнийг хэрэгжүүлэх боломжтой гэж найдаж байна уу?
- Нэг, хоёр, гурвын тэнцүү тооны мөрүүдээс бүрдэх хэлний контекст мэдрэмтгий дүрмийг зохиох үйл явцыг тайлбарла.
- Контекст мэдрэмтгий хэлний жишээг өгч, түүнийг контекст мэдрэмтгий дүрмээр хэрхэн танихыг тайлбарла.
- Рекурсив тоологдох хэл гэж нэрлэгддэг 0 төрлийн хэл нь тооцооллын нарийн төвөгтэй байдлын хувьд бусад төрлийн хэлнээс юугаараа ялгаатай вэ?
- Контекстээс ангид хэл ба контекст мэдрэмтгий хэл хоёрын ялгааг тэдгээрийн үүсэх дүрмийн дагуу тайлбарла.