Pumping lemma for context-free languages
کمپیوٹر سائنس میں، خاص طور پر رسمی زبان کے نظریہ میں، سیاق و سباق سے پاک زبانوں کے لیے پمپنگ لیما، جسے بار ہلل لیما بھی کہا جاتا ہے، ایک ایسا لیما ہے جو تمام سیاق و سباق سے پاک زبانوں کی مشترکہ خاصیت دیتا ہے اور باقاعدہ زبانوں کے لیے پمپنگ لیما کو عمومی بناتا ہے۔ پمپنگ لیما کو اس تضاد کے ذریعے ثبوت بنانے کے لیے استعمال کیا جا سکتا ہے کہ کوئی مخصوص زبان سیاق و سباق سے پاک نہیں ہے۔ اس کے برعکس، پمپنگ لیما اس بات کی ضمانت دینے کے لیے کافی نہیں ہے کہ کوئی زبان سیاق و سباق سے پاک ہے۔ دیگر ضروری شرائط بھی ہیں، جیسے اوگڈن کا لیما، یا انٹرچینج لیما۔ رسمی بیان اگر کوئی زبان سیاق و سباق سے پاک ہے، تو وہاں کچھ عدد موجود ہے (جسے "پمپنگ لمبائی" کہا جاتا ہے) جیسے کہ اس میں موجود ہر تار کی لمبائی یا زیادہ علامتیں ہوں (یعنی۔ کے ساتھ) کو سبسٹرنگ کے ساتھ لکھا جا سکتا ہے اور اس طرح کہ 1.، 2.، اور 3. سب کے لیے۔ ذیل میں پمپنگ لیما کا رسمی اظہار ہے۔ غیر رسمی بیان اور وضاحت سیاق و سباق سے پاک زبانوں کے لیے پمپنگ لیما (جسے اس مضمون کے باقی حصوں کے لیے صرف "پمپنگ لیما" کہا جاتا ہے) ایک ایسی خاصیت کی وضاحت کرتا ہے جس کی تمام سیاق و سباق سے پاک زبانوں کو ضمانت دی جاتی ہے۔ خاصیت زبان کے تمام تاروں کی خاصیت ہے جس کی لمبائی کم از کم ہوتی ہے، جہاں ایک مستقل ہوتا ہے-جسے پمپنگ لمبائی کہا جاتا ہے-جو سیاق و سباق سے پاک زبانوں کے درمیان مختلف ہوتا ہے۔ کہو لمبائی کا ایک تار ہے جو کم از کم زبان میں ہے۔ پمپنگ لیما میں کہا گیا ہے کہ اسے پانچ سبسٹرنگز میں تقسیم کیا جا سکتا ہے، جہاں خالی نہیں ہے اور اس کی لمبائی زیادہ سے زیادہ ہے، اس طرح کہ دہرانے اور ایک ہی تعداد میں () میں ایک تار پیدا ہوتا ہے جو اب بھی زبان میں ہے۔ یہ اکثر صفر بار دہرانے کے لیے مفید ہوتا ہے، جو تار سے ہٹ جاتا ہے۔ اور کی اضافی کاپیوں کے ساتھ "پمپنگ اپ" کا یہ عمل ہی پمپنگ لیما کو اس کا نام دیتا ہے۔ محدود زبانیں (جو باقاعدہ ہیں اور اس لیے سیاق و سباق سے پاک ہیں) پلس ون میں زیادہ سے زیادہ تار کی لمبائی کے برابر ہونے کی وجہ سے معمولی طور پر پمپنگ لیما کی اطاعت کرتی ہیں۔ چونکہ اس لمبائی کے کوئی تار نہیں ہیں اس لیے پمپنگ لیما کی خلاف ورزی نہیں ہوتی ہے۔ لیما کا استعمال پمپنگ لیما اکثر یہ ثابت کرنے کے لیے استعمال کیا جاتا ہے کہ دی گئی زبان غیر سیاق و سباق سے پاک ہے، یہ ظاہر کر کے کہ من مانی طور پر لمبی تار اس میں ہیں جسے باہر تار تیار کیے بغیر "پمپ" نہیں کیا جا سکتا۔ مثال کے طور پر، اگر لامحدود ہے لیکن اس میں (لامحدود) ریاضی کی ترقی نہیں ہے، تو سیاق و سباق سے پاک نہیں ہے۔ خاص طور پر، نہ تو پرائم نمبر اور نہ ہی مربع نمبر سیاق و سباق سے پاک ہیں۔ مثال کے طور پر، متضاد ثبوت میں پمپنگ لیما کا استعمال کرکے زبان کو غیر سیاق و سباق سے پاک دکھایا جا سکتا ہے۔ سب سے پہلے، فرض کریں کہ یہ سیاق و سباق سے پاک ہے۔ پمپنگ لیما سے، ایک عدد موجود ہوتا ہے جو زبان کی پمپنگ لمبائی ہے۔ سٹرنگ پر غور کریں۔ پمپنگ لیما ہمیں بتاتا ہے کہ اسے اس شکل میں لکھا جا سکتا ہے، جہاں، اور سبسٹرنگ ہیں، جیسے کہ، اور ہر عدد کے لیے۔ کے انتخاب اور اس حقیقت سے، یہ آسانی سے دیکھا جا سکتا ہے کہ سبسٹرنگ میں دو سے زیادہ الگ الگ علامتیں نہیں ہو سکتی ہیں۔ یعنی، ہمارے پاس پانچ امکانات میں سے ایک ہے: کچھ کے لیے۔ کچھ کے لیے اور کچھ کے لیے۔ کچھ کے لیے اور ساتھ۔ کچھ کے لیے۔ ہر معاملے کے لیے، اس بات کی آسانی سے تصدیق کی جاتی ہے کہ اس میں کسی کے لیے بھی ہر حرف کی مساوی تعداد نہیں ہوتی ہے۔ اس طرح، شکل نہیں ہے۔ یہ تعریف سے متصادم ہے۔ لہذا، ہمارا ابتدائی مفروضہ جو سیاق و سباق سے پاک ہے، غلط ہونا چاہیے۔ اگرچہ پمپنگ لیما اکثر یہ ثابت کرنے کے لیے ایک مفید ذریعہ ہوتا ہے کہ دی گئی زبان سیاق و سباق سے پاک نہیں ہے، لیکن یہ سیاق و سباق سے پاک زبانوں کی مکمل خصوصیت نہیں دیتا ہے۔ اگر کوئی زبان پمپنگ لیما کی دی گئی شرط کو پورا نہیں کرتی ہے، تو ہم نے ثابت کیا ہے کہ وہ سیاق و سباق سے پاک نہیں ہے۔ دوسری طرف، ایسی زبانیں ہیں جو سیاق و سباق سے پاک نہیں ہیں، لیکن پھر بھی پمپنگ لیما کی طرف سے دی گئی شرط کو پورا کرتی ہیں، مثال کے طور پر مثال کے طور پر۔ جے ≤ 1 صرف بی پر مشتمل ہونے کا انتخاب کرتا ہے، صرف اے پر مشتمل ہونے کا انتخاب کرنے کے لیے ؛ دونوں صورتوں میں تمام پمپ شدہ تار اب بھی ایل میں ہیں۔ پمپنگ لیما کا پیش خیمہ 1960 میں شینبرگ نے یہ ثابت کرنے کے لیے استعمال کیا تھا کہ یہ سیاق و سباق سے پاک نہیں ہے۔ حوالہ جات-سیکشن 1.4: غیر باقاعدہ زبانیں، پی پی۔ 77-83 میں دوبارہ چھاپے گئے۔ سیکشن 2: غیر سیاق و سباق سے پاک زبانیں، پی پی۔ 115-119۔ رسمی زبانیں لیما