В хэлний жишээн дээр яагаад a^Pb^Pc^P мөрөнд шахах шинж чанар тохирохгүй байна вэ?
Шахах шинж чанар нь шахуургын лемма гэгддэг бөгөөд контекст мэдрэмтгий хэлийг шинжлэхэд зориулсан тооцооллын нарийн төвөгтэй байдлын онолын үндсэн хэрэгсэл юм. Энэ нь тухайн хэл дээрх бүх мөрт заавал байх ёстой нөхцөлийг хангаснаар тухайн хэл контекст мэдрэмтгий эсэхийг тодорхойлоход тусалдаг. Гэсэн хэдий ч B хэл болон a^Pb^Pc^P тэмдэгтийн хувьд шахах шинж чанар хангагддаггүй.
Яагаад шахах шинж чанар нь энэ мөрөнд тохирохгүй байгааг ойлгохын тулд эхлээд контекст мэдрэмтгий хэлнүүдийн шахах лемма-г авч үзье. Леммийн дагуу хэрэв L хэл нь контекст мэдрэмтгий бол n тогтмол (шахах урт) байдаг тул L хэлэнд |w|-тэй w ямар ч мөр байх болно. ≥ n-ийг таван хэсэгт хувааж болно: w = uvxyz, дараах нөхцлийг хангана.
1. |vxy| ≤ n
2. |vy| ≥ 1
3. Бүх i ≥ 0-ийн хувьд uv^ixy^iz тэмдэгт мөр нь мөн L-д байна.
Одоо P нь анхны тоо болох a^Pb^Pc^P мөрийг авч үзье. Энэ мөр нь ижил тооны 'b' ба 'c'-ийн дараалсан 'a'-ийн дарааллаас бүрдэнэ. Энэ мөрийг w = uvxyz гэж таван хэсэгт хуваая гэж бодъё, энд |vxy| ≤ n ба |vy| ≥ 1.
Энэ тохиолдолд шахуургын урт n нь тогтмол байдаг тул шахах леммийн нөхцлийг хангасан хуваалтыг сонгох боломжгүй. Учир нь мөрөнд байгаа 'a, 'b, 'c'-ийн тоо тогтмол бөгөөд P-тэй тэнцүү байх бөгөөд энэ нь анхны тоо юм. Иймд шахуургын утсанд байгаа “а”, “б”, “в”-ийн тоо хэвээр байхаар утсыг таван хэсэгт хуваах боломжгүй.
Жишээлбэл, vxy нь зөвхөн "a"-аас бүрдэх боломжтой хуваалтыг авч үзье. Энэ тохиолдолд 'a'-ийн илтгэгчийг нэмэгдүүлэх замаар шахах нь 'b' ба 'c'-тэй харьцуулахад өөр тооны 'a-тай тэмдэгт мөр үүсэх бөгөөд бүх шахагдсан мөрүүд хэл дээр байх ёстой гэсэн нөхцөлийг зөрчинө. Үүнтэй адилаар бусад боломжит хуваалт нь шахуургын лемма нөхцлийг зөрчихөд хүргэдэг.
Тиймээс бид B хэлний жишээн дэх a^Pb^Pc^P мөрт шахах шинж чанар тохирохгүй байна гэж дүгнэж болно. Энэ нь a^Pb^Pc^P хэлбэрийн мөрүүдийг агуулсан В хэл, контекст мэдрэмтгий хэл биш.
a^Pb^Pc^P тэмдэгт мөр нь 'a, 'b', 'c'-ийн тогтмол ба анхны тоонуудаас шалтгаалан контекст мэдрэмтгий хэлнүүдийн шахах леммийн нөхцлийг хангаж чадахгүй. Шахах шинж чанарыг зөрчсөн нь энэ мөрийг агуулсан В хэл нь контекст мэдрэмтгий хэл биш гэдгийг харуулж байна.
Сүүлийн үеийн бусад асуулт, хариулт Агуулгын мэдрэмжтэй хэл:
- Хомскийн дүрмийн хэвийн хэлбэрийг үргэлж шийдвэрлэх боломжтой юу?
- Type-0-ийг таних одоогийн аргууд байдаг уу? Бид квант компьютерууд үүнийг хэрэгжүүлэх боломжтой гэж найдаж байна уу?
- D хэлний жишээн дээр шахах шинж чанар яагаад S = 0^P 1^P 0^P 1^P мөрөнд тохирохгүй байна вэ?
- Шахах лемма хэрэглэхийн тулд утсыг хуваахдаа ямар хоёр тохиолдолд анхаарах ёстой вэ?
- Ус шахах объектыг барихын тулд ямар нөхцөлийг хангасан байх ёстой вэ?
- Хэл нь контекстээс ангид биш гэдгийг батлахын тулд CFL-д зориулсан Pumping Lemma-г хэрхэн ашиглах вэ?
- Контекстгүй хэлнүүдийн шахах lemma-ийн дагуу тухайн хэлийг контекстгүй гэж үзэхийн тулд ямар нөхцөл хангасан байх ёстой вэ?
- Рекурсын тухай ойлголтыг контекстээс ангид дүрмийн хүрээнд тайлбарлаж, урт мөр үүсгэх боломжийг хэрхэн олгодог талаар тайлбарлана уу.
- Задлан задлах мод гэж юу вэ, түүнийг контекстгүй дүрмийн дагуу үүсгэсэн мөрийн бүтцийг төлөөлөхөд хэрхэн ашигладаг вэ?
- Контекстгүй хэлийг хэрхэн тодорхойлдог вэ, контекстгүй дүрмийн бүрэлдэхүүн хэсгүүд юу вэ?
Контекст мэдрэмтгий хэл дээр илүү олон асуулт, хариултыг харна уу