Контекст мэдрэмтгий хэлүүд (CSLs) нь контекст мэдрэмтгий дүрмээр тодорхойлогддог албан ёсны хэлний анги юм. Эдгээр дүрмүүд нь контекстээс ангид дүрмийн ерөнхий дүрмүүд бөгөөд солих нь тодорхой нөхцөл байдалд тохиолдсон тохиолдолд мөрийг өөр тэмдэгт мөрөөр орлуулах үйлдвэрлэлийн дүрмийг зөвшөөрдөг. Хэлний энэ анги нь контекстгүй хэлнүүдээс илүү хүчтэй боловч рекурсив тоолох боломжтой хэлнээс бага чадалтай тул тооцооллын онолд чухал ач холбогдолтой.
Контекст мэдрэмтгий хэлийг Тьюрингийн машинаар таних эсэх нь тооцооллын загваруудын боломж, хязгаарлалтыг ойлгоход чухал ач холбогдолтой юм. Үүнийг шийдвэрлэхийн тулд контекст мэдрэмтгий хэл болон Тюринг машинуудын тодорхойлолт, шинж чанарыг харгалзан үзэх нь чухал юм.
Тюринг машин нь хязгааргүй соронзон хальс, тэмдэгтүүдийг уншиж бичиж чаддаг соронзон хальсны толгой, хязгаарлагдмал төлөв байдлын багцаас бүрдэх хийсвэр тооцооллын загвар юм. Энэ нь одоогийн төлөв болон уншиж буй тэмдэгт дээр суурилсан дүрмийн багцын дагуу мужуудын хооронд шилжих замаар ажилладаг. Тьюрингийн машинууд нь ямар ч алгоритмыг дуурайх чадвараараа алдартай бөгөөд үүнийг Сүмийн-Тюрингийн диссертацид багтаасан болно. Энэхүү дипломын ажил нь алгоритмаар тооцоолж болох аливаа функцийг Тьюрингийн машинаар тооцоолж болно гэж үздэг.
Контекст мэдрэмтгий хэлүүд нь контекст мэдрэмтгий дүрмээр тодорхойлогддог бөгөөд тэдгээр нь αAβ → αγβ хэлбэрийн үйлдвэрлэлийн дүрэмтэй байдаг ба энд A нь терминалгүй, α, β, γ нь терминал ба/эсвэл терминалын бус мөрүүд юм. Гол хязгаарлалт нь баруун гар талын утаснуудын урт нь зүүн гар талын утаснаас багагүй урт байх ёстой. Энэ нь үүсгэсэн хэл нь гэрээ хэлцэлгүй гэдгийг баталгаажуулдаг бөгөөд үүсмэл хэллэг нь мөрийн уртыг багасгаж чадахгүй гэсэн үг юм.
Тьюрингийн машинуудын хүлээн зөвшөөрсөн хэлнүүдийн ангилал нь рекурсив тоолох боломжтой хэлний ангилал юм. Тухайн хэл дээрх дурын мөрийг хүлээн авч, тухайн хэл дээр байхгүй мөрүүд дээр зогсох юм уу тодорхойгүй хугацаагаар давтагдах Тьюрингийн машин байгаа бол хэлийг рекурсив байдлаар тоолж болно. Контекст мэдрэмтгий хэлүүд нь рекурсив тоолох боломжтой хэлнүүдийн нэг хэсэг бөгөөд энэ нь контекст мэдрэмтгий хэлийг Тьюрингийн машинаар таних боломжтой гэсэн үг юм.
Үүнийг харуулахын тулд Турингийн машины хязгаарлагдмал хэлбэр болох Linear Bounded Automaton (LBA) -ийг авч үзье. LBA нь оролтын хэмжээн дэх зарим шугаман функцээр хязгаарлагдах соронзон хальстай, детерминистик бус Тьюрингийн машин юм. Энэ хязгаарлалт нь LBA нь оролтын мөр болон хязгаарлагдмал хэмжээний туслах мэдээллийг хадгалахад шаардагдахаас илүү соронзон хальс ашиглах боломжгүй гэсэн үг юм. Контекст мэдрэмтгий хэлүүд нь LBA-ийн хүлээн зөвшөөрдөг хэлний ангилал юм. LBA нь хязгаарлагдмал соронзон хальсны хэрэглээтэй хэдий ч Turing Machine-ийн нэг төрөл учраас контекст мэдрэмтгий хэлүүдийг Тьюрингийн машинууд таних боломжтой.
Энэхүү таних чадвар нь Тьюрингийн машин нь LBA-г дуурайж чаддагтай холбоотой юм. Хэдийгээр LBA нь соронзон хальсны хэрэглээнд хязгаарлалттай байдаг ч Turing Machine нь соронзон хальсны хил хязгаарыг хянах нэмэлт төлөвүүдийг ашиглан энэ зан үйлийг дуурайж чаддаг. Энэхүү симуляци нь Тьюрингийн машин нь LBA шиг ажиллаж, контекст мэдрэмтгий хэлүүдийг таних боломжийг олгодог.
Цаашид тайлбарлахын тулд хэлийг авч үзье L = { a^nb^nc^n | n ≥ 1 }, энэ нь контекст мэдрэмтгий хэлний сонгодог жишээ юм. Контекстгүй дүрмүүд нь мөрийн олон хэсгүүдийн хоорондын хамаарлыг хэрэгжүүлэх чадваргүй тул энэ хэлийг контекстгүй дүрмээр үүсгэх боломжгүй. Гэхдээ үүнийг S → aSBc | гэх мэт дүрмүүдтэй контекст мэдрэмжтэй дүрмээр үүсгэж болно. abc болон Bc → bC, бусад. LBA-г энэ хэлийг танихын тулд "a", "b" болон "c"-ийн тоог тэнцүү байлгахын тулд хязгаарлагдмал туузыг ашиглан хийж болно.
Тьюрингийн машины контекст мэдрэмтгий хэлийг таних чадвар нь зөвхөн онолын хувьд биш, харин тооцооллын хэл шинжлэл, програмчлалын хэлэнд практик ач холбогдолтой юм. Олон програмчлалын хэлүүд нь контекст мэдрэмтгий синтаксийн бүтэцтэй байдаг бөгөөд контекстээс ангид дүрмээс давсан задлан шинжлэх арга техникийг шаарддаг. Тьюрингийн машинууд нь ерөнхий шинж чанараараа дамжуулан эдгээр хэлний задлан шинжлэгчийг ойлгох, хэрэгжүүлэх хүрээг бүрдүүлдэг.
Тооцооллын нарийн төвөгтэй байдлын онолд контекст мэдрэмтгий хэлүүд нь PSPACE төвөгтэй байдлын ангитай холбоотой байдаг. Энэ анги нь олон гишүүнт орон зайг ашиглан Тьюрингийн машинаар шийдэж болох шийдвэрийн бодлогоос бүрдэнэ. Тьюрингийн машин контекст мэдрэмтгий хэлүүдийг хүлээн зөвшөөрсөн нь эдгээр хэлийг хүлээн зөвшөөрдөг LBA нь олон гишүүнт орон зайн хязгаарлалтын хүрээнд ажилладаг тул энэ нарийн төвөгтэй байдлын ангилалд нийцдэг.
Контекст мэдрэмтгий хэлүүдийг Тьюрингийн машинууд үнэхээр таних боломжтой. Тюринг машинууд контекст мэдрэмтгий хэлийг хүлээн авахаар тусгайлан бүтээгдсэн шугаман хязгаарлагдмал автоматуудыг дуурайлган хийх чадвар нь энэхүү танигдлыг хөнгөвчилдөг. Энэхүү харилцаа нь албан ёсны хэлний онол, тооцооллын нарийн төвөгтэй байдлын хүрээнд Тьюрингийн машинуудын хүч чадал, уян хатан чанарыг онцолж өгдөг.
Сүүлийн үеийн бусад асуулт, хариулт EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс:
- Палиндромыг уншиж чаддаг PDA-г авч үзвэл оролт нь нэгдүгээрт, палиндром, хоёрдугаарт палиндром биш байх үед стекийн хувьслыг нарийвчлан хэлж чадах уу?
- Детерминистик бус PDA-уудыг авч үзвэл мужуудын суперпозиция нь тодорхойлолтоор боломжтой юм. Гэсэн хэдий ч детерминистик бус PDA нь зөвхөн нэг стектэй байдаг бөгөөд энэ нь нэгэн зэрэг олон төлөвт байж болохгүй. Энэ яаж боломжтой вэ?
- Сүлжээний урсгалд дүн шинжилгээ хийх, аюулгүй байдлын болзошгүй зөрчлийг илтгэх хэв маягийг тодорхойлоход ашигладаг PDA-ийн жишээ юу вэ?
- Нэг хэл нөгөө хэлээсээ илүү хүчтэй гэдэг нь юу гэсэн үг вэ?
- U = 0^n1^n (n>=0) хэл яагаад тогтмол бус байна вэ?
- Тэгш тооны '1' тэмдэгт бүхий хоёртын мөрийг таних FSM-г хэрхэн тодорхойлж, 1011 оролтын мөрийг боловсруулахад юу болдгийг харуулах вэ?
- Нотертерминизм нь шилжилтийн функцэд хэрхэн нөлөөлдөг вэ?
- Энгийн хэлүүд нь хязгаарлагдмал төрийн машинуудтай тэнцэх үү?
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- Алгоритмын хувьд тооцоолж болох асуудал нь Тьюрингийн машинаар тооцоолж болох асуудал мөн үү?