سیاق و سباق سے پاک گرائمر کو پارس کرنے میں گرامر کے ذریعہ بیان کردہ پیداواری قواعد کے ایک سیٹ کے مطابق علامتوں کی ترتیب کا تجزیہ کرنا شامل ہے۔ یہ عمل کمپیوٹر سائنس کے مختلف شعبوں میں بنیادی ہے، بشمول سائبرسیکیوریٹی، کیونکہ یہ ہمیں سٹرکچرڈ ڈیٹا کو سمجھنے اور اس میں ہیرا پھیری کرنے کی اجازت دیتا ہے۔ اس جواب میں، ہم سیاق و سباق سے پاک گرائمر کو پارس کرنے کے الگورتھم کی وضاحت کریں گے اور اس کے وقت کی پیچیدگی پر تبادلہ خیال کریں گے۔
سیاق و سباق سے پاک گرامر کو پارس کرنے کے لیے سب سے زیادہ استعمال ہونے والا الگورتھم CYK الگورتھم ہے، جس کا نام اس کے موجد کوک، ینگر اور کسامی کے نام پر رکھا گیا ہے۔ یہ الگورتھم ڈائنامک پروگرامنگ پر مبنی ہے اور باٹم اپ پارسنگ کے اصول پر کام کرتا ہے۔ یہ ایک پارس ٹیبل بناتا ہے جو ان پٹ کے ذیلی اسٹرنگ کے لیے تمام ممکنہ پارس کی نمائندگی کرتا ہے۔
CYK الگورتھم اس طرح کام کرتا ہے:
1. ایک پارس ٹیبل کو ڈائمینشنز nxn کے ساتھ شروع کریں، جہاں n ان پٹ سٹرنگ کی لمبائی ہے۔
2. ان پٹ سٹرنگ میں ہر ٹرمینل علامت کے لیے، پارس ٹیبل میں متعلقہ سیل کو ان غیر ٹرمینل علامتوں سے بھریں جو اسے تیار کرتے ہیں۔
3. ہر ذیلی اسٹرنگ کی لمبائی l 2 سے n تک، اور ہر ابتدائی پوزیشن i 1 سے n-l+1 تک، درج ذیل کام کریں:
a i سے i+l-2 تک ہر پارٹیشن پوائنٹ کے لیے، اور ہر پروڈکشن قاعدہ 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 | a
B -> AB | ب
C -> BC | c
اور ان پٹ سٹرنگ "abc"۔ اس مثال کے لیے پارس ٹیبل اس طرح نظر آئے گا:
| 1 | 2 | 3 |
——-|—–|—–|—–|
1 | A,S | بی، سی | ایس |
——-|—–|—–|—–|
2 | | بی، سی | ایک |
——-|—–|—–|—–|
3 | | | سی |
——-|—–|—–|—–|
اس جدول میں، سیل (1، 3) میں شروع کی علامت S ہے، جس سے ظاہر ہوتا ہے کہ ان پٹ سٹرنگ "abc" کو دی گئی گرامر سے اخذ کیا جا سکتا ہے۔
سیاق و سباق سے پاک گرائمر کو پارس کرنے کا الگورتھم، جیسا کہ CYK الگورتھم، ہمیں سٹرکچرڈ ڈیٹا کا تجزیہ اور سمجھنے کی اجازت دیتا ہے۔ یہ پارس ٹیبل بنا کر اور گرائمر کے پروڈکشن قواعد کے مطابق درست اخذات کی جانچ کر کے کام کرتا ہے۔ CYK الگورتھم کی وقتی پیچیدگی O(n^3 * |G|) ہے، جہاں n ان پٹ سٹرنگ کی لمبائی ہے اور |G| گرامر کا سائز ہے۔
سے متعلق دیگر حالیہ سوالات اور جوابات پیچیدگی:
- کیا PSPACE کلاس EXPSPACE کلاس کے برابر نہیں ہے؟
- کیا P پیچیدگی کلاس PSPACE کلاس کا سب سیٹ ہے؟
- کیا ہم یہ ثابت کر سکتے ہیں کہ Np اور P کلاس یکساں ہیں کسی بھی NP مکمل مسئلے کے لیے ایک مؤثر کثیر الثانی حل تلاش کر کے ایک deterministic TM پر؟
- کیا NP کلاس EXPTIME کلاس کے برابر ہو سکتی ہے؟
- کیا PSPACE میں ایسے مسائل ہیں جن کے لیے کوئی معلوم NP الگورتھم نہیں ہے؟
- کیا SAT کا مسئلہ NP مکمل مسئلہ ہوسکتا ہے؟
- کیا NP پیچیدگی کی کلاس میں کوئی مسئلہ ہو سکتا ہے اگر کوئی نان ڈیٹرمنسٹک ٹیورنگ مشین ہو جو اسے کثیر وقت میں حل کر دے
- NP زبانوں کی کلاس ہے جس میں متعدد وقت کی تصدیق ہوتی ہے۔
- کیا P اور NP دراصل ایک ہی پیچیدگی کی کلاس ہے؟
- کیا P پیچیدگی کی کلاس میں ہر سیاق و سباق سے پاک زبان ہے؟
Complexity میں مزید سوالات اور جوابات دیکھیں