Контекстгүй хэл гэдэг нь контекстгүй дүрмийн тусламжтайгаар дүрсэлж болох албан ёсны хэлний нэг төрөл юм. Тооцооллын нарийн төвөгтэй байдлын онолын салбарт контекстгүй хэл нь асуудлын нарийн төвөгтэй байдал, тооцооллын хязгаарыг ойлгоход чухал үүрэг гүйцэтгэдэг. Контекстгүй хэлний тухай ойлголтыг бүрэн ойлгохын тулд түүний тодорхойлолт болон контекстгүй дүрмийн бүрэлдэхүүн хэсгүүдийг судлах нь чухал юм.
Контекстгүй хэл гэдэг нь контекстгүй дүрмийн дагуу үүсгэж болох мөрүүдийн багц гэж тодорхойлогддог. Контекстгүй дүрэм нь терминалын бус тэмдэгтүүд, терминал тэмдэгтүүдийн багц, үйлдвэрлэлийн дүрмийн багц, эхлэлийн тэмдэг гэсэн дөрвөн бүрэлдэхүүн хэсгээс бүрдэнэ.
Терминал бус тэмдэгтүүд нь хийсвэр объектуудыг төлөөлдөг бөгөөд тэдгээрийг цаашид өргөжүүлэх эсвэл өөр тэмдэгтээр сольж болно. Эдгээр тэмдэглэгээг ихэвчлэн том үсгээр илэрхийлдэг. Жишээлбэл, арифметик хэллэгийн контекстгүй дүрмийн хувьд бид E (илэрхийллийг илэрхийлэх), T (нэр томьёог илэрхийлэх), F (хүчин зүйлийг илэрхийлэх) зэрэг терминалын бус тэмдэгтүүдтэй байж болно.
Нөгөө талаас терминал тэмдэгтүүд нь хэлний анхан шатны нэгж юм. Эдгээр тэмдэглэгээг цаашид өргөжүүлэх боломжгүй бөгөөд ихэвчлэн жижиг үсэг эсвэл бусад тэмдэгтээр илэрхийлэгддэг. Арифметик илэрхийллийн хүрээнд терминалын тэмдэгтүүд нь тоонууд (жишээ нь: 0, 1, 2) болон арифметик операторуудыг (жишээ нь, +, -, *, /) агуулж болно.
Үйлдвэрлэлийн дүрмүүд нь терминалын бус тэмдэгтүүдийг хэрхэн өргөжүүлэх эсвэл бусад тэмдгээр сольж болохыг тодорхойлдог. Үйлдвэрлэлийн дүрэм бүр нь зүүн талд байрлах терминалын бус тэмдэг, баруун талд байгаа тэмдэгтүүдийн дараалал (терминал болон терминалын аль аль нь) -аас бүрдэнэ. Эдгээр дүрмүүд нь хэл дээр хүчинтэй мөр үүсгэхийн тулд хэрэглэж болох хувиргах эсвэл үүсмэл хувилбаруудыг зааж өгдөг. Жишээлбэл, арифметик хэллэгийн контекстгүй дүрмийн хувьд бид E -> E + T (нэг томьёо нэмснээр илэрхийлэлийг өргөтгөж болно) эсвэл T -> F (нэр томьёо байж болохыг заана) гэх мэт үйлдвэрлэлийн дүрэмтэй байж болно. хүчин зүйлээр сольсон).
Эхлэх тэмдэг нь хүчинтэй мөрүүдийг үүсгэх эхлэлийн терминалын бус тэмдгийг илэрхийлдэг. Үүнийг ихэвчлэн S-ээр тэмдэглэдэг. Арифметик илэрхийллийн нөхцөлд эхлэлийн тэмдэг нь E байж болох бөгөөд энэ нь хүчинтэй илэрхийлэл үүсгэх нь илэрхийллээс эхэлдэг болохыг харуулж байна.
Контекстгүй хэл ба түүний бүрэлдэхүүн хэсгүүдийн тухай ойлголтыг тайлбарлахын тулд тэнцвэртэй хашилт үүсгэдэг хэлний энгийн контекстгүй дүрмийг авч үзье. Дүрэм нь дараах бүрэлдэхүүн хэсгүүдээс бүрдэнэ.
Терминал бус тэмдэг: S (эхлэх тэмдэг)
Терминал тэмдэг: (, )
Үйлдвэрлэлийн дүрэм: S -> (S) | SS | ε (энд ε нь хоосон мөрийг илэрхийлнэ)
Энэ дүрмийн хувьд төгсгөлийн бус S тэмдэгт нь тэнцвэртэй хашилтын мөрийг төлөөлдөг. Үйлдвэрлэлийн дүрмүүд нь хаалтанд ((S) өөр S-г оруулах), хоёр S-г (SS) холбох эсвэл хоосон мөр (ε) үүсгэх замаар S-г өргөтгөж болно гэж заасан байдаг.
Энэхүү дүрмийг ашигласнаар бид тэнцвэртэй хашилтын хэлээр хүчинтэй мөрүүдийг үүсгэж болно. Жишээлбэл, S эхлэлийн тэмдэгээс эхлэн бид ((())) мөрийг гаргахын тулд үйлдвэрлэлийн дүрмийг хэрэглэж болно. Энэ мөр нь тэнцвэртэй хаалтуудын дарааллыг илэрхийлнэ.
Контекстгүй хэл гэдэг нь контекстгүй дүрмийн дагуу үүсгэж болох мөрүүдийн багц гэж тодорхойлогддог. Контекстгүй дүрмийн бүрэлдэхүүн хэсгүүдэд терминалын бус тэмдэгтүүд, терминалын тэмдэгтүүд, үйлдвэрлэлийн дүрэм, эхлэлийн тэмдэг орно. Терминал бус тэмдэгтүүд нь өргөтгөх эсвэл солих боломжтой хийсвэр объектуудыг төлөөлдөг бол терминал тэмдэгтүүд нь хэлний анхан шатны нэгжүүд юм. Үйлдвэрлэлийн дүрмүүд нь боломжит хувиргалт эсвэл гарал үүслийг зааж өгөх ба эхлэх тэмдэг нь хүчинтэй мөрүүдийг үүсгэх анхны терминалын бус тэмдгийг илэрхийлдэг.
Сүүлийн үеийн бусад асуулт, хариулт Агуулгын мэдрэмжтэй хэл:
- Нэг хэл нөгөө хэлээсээ илүү хүчтэй гэдэг нь юу гэсэн үг вэ?
- Хомскийн дүрмийн хэвийн хэлбэрийг үргэлж шийдвэрлэх боломжтой юу?
- Type-0-ийг таних одоогийн аргууд байдаг уу? Бид квант компьютерууд үүнийг хэрэгжүүлэх боломжтой гэж найдаж байна уу?
- D хэлний жишээн дээр шахах шинж чанар яагаад S = 0^P 1^P 0^P 1^P мөрөнд тохирохгүй байна вэ?
- Шахах лемма хэрэглэхийн тулд утсыг хуваахдаа ямар хоёр тохиолдолд анхаарах ёстой вэ?
- В хэлний жишээн дээр яагаад a^Pb^Pc^P мөрөнд шахах шинж чанар тохирохгүй байна вэ?
- Ус шахах объектыг барихын тулд ямар нөхцөлийг хангасан байх ёстой вэ?
- Хэл нь контекстээс ангид биш гэдгийг батлахын тулд CFL-д зориулсан Pumping Lemma-г хэрхэн ашиглах вэ?
- Контекстгүй хэлнүүдийн шахах lemma-ийн дагуу тухайн хэлийг контекстгүй гэж үзэхийн тулд ямар нөхцөл хангасан байх ёстой вэ?
- Рекурсын тухай ойлголтыг контекстээс ангид дүрмийн хүрээнд тайлбарлаж, урт мөр үүсгэх боломжийг хэрхэн олгодог талаар тайлбарлана уу.
Контекст мэдрэмтгий хэл дээр илүү олон асуулт, хариултыг харна уу