Контекстгүй дүрмийг задлан шинжлэх алгоритм болон түүний цаг хугацааны нарийн төвөгтэй байдлыг тайлбарлана уу.
Контекстгүй дүрмийг задлан шинжлэх нь дүрмээр тодорхойлсон үйлдвэрлэлийн дүрмийн дагуу тэмдэгтүүдийн дарааллыг шинжлэх явдал юм. Энэхүү үйл явц нь компьютерийн шинжлэх ухааны янз бүрийн салбарт, тэр дундаа кибер аюулгүй байдлыг хангахад чухал ач холбогдолтой бөгөөд энэ нь бидэнд бүтэцлэгдсэн өгөгдлийг ойлгох, удирдах боломжийг олгодог. Энэ хариултанд бид контекстгүй дүрмийг задлан шинжлэх алгоритмыг тайлбарлаж, цаг хугацааны нарийн төвөгтэй байдлын талаар ярилцах болно.
Контекстгүй дүрмүүдийг задлан шинжлэхэд хамгийн түгээмэл хэрэглэгддэг алгоритм нь зохион бүтээгч Коке, Янгер, Касами нарын нэрээр нэрлэгдсэн CYK алгоритм юм. Энэхүү алгоритм нь динамик програмчлалд суурилсан бөгөөд доороос дээш задлан шинжлэх зарчмаар ажилладаг. Энэ нь оролтын дэд мөрүүдэд зориулсан бүх боломжит задлан шинжлэх хүснэгтийг бүтээдэг.
CYK алгоритм нь дараах байдлаар ажилладаг.
1. nxn хэмжээс бүхий задлан шинжилсэн хүснэгтийг эхлүүлэх ба энд n нь оролтын мөрийн урт юм.
2. Оролтын мөр дэх терминалын тэмдэг бүрийн хувьд задлан шинжлэлийн хүснэгтийн харгалзах нүдийг түүнийг үүсгэгч терминалын бус тэмдэгтүүдээр бөглөнө үү.
3. l 2-оос n хүртэлх дэд мөр бүрийн урт ба 1-ээс n-l+1 хүртэлх i байрлал бүрийн хувьд дараах зүйлийг хийнэ үү.
а. i-ээс i+l-2 хүртэлх p хуваалтын цэг бүрийн хувьд, үйлдвэрлэлийн дүрэм A -> BC бүрийн хувьд (i, p) болон (p+1, i+l-1) нүднүүд нь B ба C төгсгөлийн бус тэмдэгтүүдийг агуулж байгаа эсэхийг шалгана уу. , тус тус. Хэрэв тийм бол нүдэнд A-г нэмнэ (i, i+l-1).
4. Хэрэв дүрмийн эхлэлийн тэмдэг нүдэнд (1, n) байгаа бол оролтын мөрийг дүрмээс гаргаж болно. Тэгэхгүй бол болохгүй.
CYK алгоритмын цагийн нарийн төвөгтэй байдал нь O(n^3 * |G|), энд n нь оролтын мөрийн урт ба |G| дүрмийн хэмжээ юм. Энэхүү нарийн төвөгтэй байдал нь задлан шинжлэлийн хүснэгтийг бөглөхөд ашигладаг үүрлэсэн гогцоонуудаас үүсдэг. Алгоритм нь бүх боломжит хуваалтын цэгүүд болон дэд мөрийн урт бүрийн үйлдвэрлэлийн дүрмийг судалж, куб цагийн нарийн төвөгтэй байдлыг үүсгэдэг.
Алгоритмыг харуулахын тулд дараах контекстгүй дүрмийг анхаарч үзээрэй.
S -> AB | МЭӨ
A -> AA | а
B -> AB | б
C -> BC | в
Мөн "abc" оролтын мөр. Энэ жишээний задлан шинжлэх хүснэгт дараах байдлаар харагдах болно.
| 1 | 2 | 3 |
——-|—–|—–|—–|
1 | A,S | B,C | S |
——-|—–|—–|—–|
2 | | B,C | А |
——-|—–|—–|—–|
3 | | | C |
——-|—–|—–|—–|
Энэ хүснэгтийн нүд (1, 3) нь өгөгдсөн дүрмийн дагуу "abc" оролтын мөрийг гаргаж болохыг харуулж байгаа S эхлэлийн тэмдгийг агуулсан байна.
CYK алгоритм гэх мэт контекстгүй дүрмийг задлан шинжлэх алгоритм нь бүтэцлэгдсэн өгөгдлийг шинжлэх, ойлгох боломжийг бидэнд олгодог. Энэ нь дүрмийн үйлдвэрлэлийн дүрмийн дагуу задлан шинжилсэн хүснэгтийг байгуулж, хүчинтэй үүсмэл үгсийг шалгах замаар ажилладаг. CYK алгоритмын цагийн нарийн төвөгтэй байдал нь O(n^3 * |G|) бөгөөд n нь оролтын мөрийн урт ба |G| дүрмийн хэмжээ юм.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу