P төвөгтэй байдлын ангид контекстгүй хэл бүр байдаг уу?
Контекстгүй хэл (CFL) бүр нарийн төвөгтэй байдлын P ангилалд багтах эсэх нь тооцооллын нарийн төвөгтэй байдлын онолын сонирхолтой сэдэв юм. Энэ асуултыг цогцоор нь шийдвэрлэхийн тулд контекстгүй хэлний тодорхойлолт, ээдрээний P анги, эдгээр ойлголтуудын хоорондын хамаарлыг авч үзэх нь чухал юм.
Контекстгүй хэл гэдэг нь контекстгүй дүрмийн (CFG) ашиглан үүсгэж болох албан ёсны хэлний нэг төрөл юм. CFG нь өгөгдсөн албан ёсны хэл дээрх бүх боломжит мөрүүдийг дүрсэлсэн үйлдвэрлэлийн дүрмийн багц юм. CFG-ийн дүрэм бүр нь терминалын бус нэг тэмдэгтийг терминал болон терминалын тэмдэгтүүдийн мөрөөр орлуулдаг. Контекстгүй хэлүүд нь ихэнх програмчлалын хэлнүүдийн синтаксийг дүрсэлж чаддаг, түлхэх автоматаар танигддаг тул компьютерийн шинжлэх ухаанд чухал ач холбогдолтой.
Нарийн төвөгтэй байдлын P анги нь олон гишүүнт цаг хугацаанд детерминист Тьюрингийн машинаар шийдэж болох шийдвэрийн бодлогоос бүрдэнэ. Олон гишүүнт цагийг O(n^k) гэж тэмдэглэсэн бөгөөд n нь оролтын хэмжээ, k нь тогтмол бөгөөд алгоритмын цаг хугацааны нарийн төвөгтэй байдлын дээд хязгаарыг илэрхийлнэ. Оролтын хэмжээ нэмэгдэхийн хэрээр тэдгээрийг шийдвэрлэхэд шаардагдах хугацаа нь зохицуулагдах хурдаар нэмэгддэг тул P дахь асуудлыг үр дүнтэй шийдвэрлэх боломжтой гэж үздэг.
Контекстгүй хэл болгон P хэл дээр байгаа эсэхийг тодорхойлохын тулд бид контекстгүй хэлээр гишүүнчлэлийн асуудлыг шийдэхэд шаардагдах тооцооллын нөөцийг шалгах ёстой. Контекстгүй хэлний шийдвэрийн асуудлыг ерөнхийд нь дараах байдлаар илэрхийлдэг: w мөр ба контекстгүй G дүрмийн дагуу G-ээр w-г үүсгэж болох эсэхийг тодорхойлно.
Контекстгүй хэлээр гишүүнчлэлийн шийдвэр гаргах стандарт алгоритм нь динамик програмчлалын алгоритм болох CYK (Cocke-Younger-Kasami) алгоритм юм. CYK алгоритм нь O(n^3) хугацаанд ажилладаг ба энд n нь оролтын мөрийн урт юм. Энэхүү куб цагийн нарийн төвөгтэй байдал нь алгоритм нь оролтын мөрийн урт болон дүрмийн төгсгөлийн бус тэмдэгтүүдийн тоотой пропорциональ хэмжээс бүхий задлан шинжлэх хүснэгтийг бүтээдэг тул үүсдэг.
CYK алгоритм нь олон гишүүнт хугацаанд ажилладаг тул контекстгүй хэлнүүдийн гишүүнчлэлийн асуудлыг олон гишүүнт хугацаанд шийдэж болно гэсэн үг. Иймээс контекстгүй хэлүүд нь нарийн төвөгтэй байдлын P ангилалд багтдаг. Энэ үр дүн нь ердийн хэлээс илүү илэрхийлэлтэй контекстгүй хэлүүдийг үр дүнтэй шийдвэрлэх боломжтойг харуулж байгаа тул чухал ач холбогдолтой юм.
Үүнийг харуулахын тулд контекстгүй хэлийг авч үзье L = {a^nb^n | n ≥ 0}, энэ нь тэнцүү тооны 'a, дараа нь тэнцүү тооны' b тэмдэгтүүдтэй мөрүүдээс бүрдэнэ. Энэ хэлний контекстгүй дүрмийг дараах байдлаар тодорхойлж болно.
S → aSb | ε
Энд S нь эхлэлийн тэмдэг, ε нь хоосон мөрийг илэрхийлнэ. CYK алгоритм нь өгөгдсөн w тэмдэгт мөр L-д хамаарах эсэхийг тодорхойлоход ашиглагдаж болно. Жишээлбэл, w = "aaabbb" мөрийг өгвөл CYK алгоритм нь w-г дүрмээр үүсгэж болохыг шалгахын тулд задлан шинжлэлийн хүснэгтийг байгуулна.
Нэмж дурдахад зарим контекстгүй хэлийг CYK алгоритмын ерөнхий O(n^3) цагийн нарийн түвэгтэй байдлаас ч илүү үр дүнтэйгээр шийдэж болохыг тэмдэглэх нь зүйтэй. Жишээлбэл, детерминист түлхэх автоматаар хүлээн зөвшөөрөгдсөн контекстгүй хэлнүүдийн дэд хэсэг болох детерминист контекстгүй хэлүүдийг ихэвчлэн O(n) хугацаанд шийдэж болно. Детерминист түлхэх автоматууд нь илүү хязгаарлагдмал тооцооллын загвартай тул хөрвүүлэгчийн загварт хэрэглэгддэг LR(k) эсвэл LL(k) задлан шинжлэлийн алгоритмуудыг илүү үр дүнтэй ашиглах боломжийг олгодог учраас цаг хугацааны шугаман нарийн төвөгтэй байдал үүсдэг.
Контекстгүй хэлнүүдийн гишүүнчлэлийн асуудлыг CYK алгоритм гэх мэт алгоритмуудыг ашиглан олон гишүүнт хугацаанд шийдэж, контекстгүй хэлүүдийг төвөгтэй байдлын P ангилалд оруулах боломжтой. Энэ үр дүн нь контекстгүй хэлүүдийг боловсруулах үр ашгийг онцолж, тэдгээрийг болгодог. програмчлалын хэлний синтакс шинжилгээ болон албан ёсны хэлийг таних шаардлагатай бусад салбарт хэрэглэхэд тохиромжтой.
Сүүлийн үеийн бусад асуулт, хариулт Харьцуулалт:
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- P нарийн төвөгтэй байдлын анги нь PSPACE ангийн дэд олонлог мөн үү?
- Детерминист TM дээр ямар ч NP бүрэн бодлогын үр ашигтай олон гишүүнт шийдийг олсноор Np ба P анги ижил гэдгийг баталж чадах уу?
- NP анги нь EXPTIME ангитай тэнцүү байж чадах уу?
- PSPACE-д тодорхой NP алгоритм байхгүй асуудал байна уу?
- SAT-ийн асуудал нь NP-ийн бүрэн асуудал байж болох уу?
- Хэрэв олон гишүүнт хугацаанд шийдвэрлэх тодорхой бус турингийн машин байгаа бол асуудал NP нарийн төвөгтэй байдлын ангилалд байж болох уу?
- NP нь олон гишүүнт цаг шалгагчтай хэлний анги юм
- P болон NP нь яг ижил нарийн төвөгтэй байдлын анги мөн үү?
- NP-г олон гишүүнт-цаг хугацааны шалгагчтай шийдвэрийн бодлогуудын анги гэж тодорхойлсон нь P ангиллын бодлогод олон гишүүнт-цаг хугацааны шалгагчтай байдгийн хооронд зөрчилдөөн байна уу?
Илүү олон асуулт, хариултыг Нарийн төвөгтэй байдлаас харна уу