Conjunctive grammar
کنجکٹو گرائمر رسمی زبان کے نظریہ میں زیر مطالعہ رسمی گرائمر کی ایک کلاس ہے۔ وہ کنجکشن آپریشن کے ساتھ بنیادی قسم کے گرائمرز، سیاق و سباق سے پاک گرائمرز کو بڑھاتے ہیں۔ واضح کنجکشن کے علاوہ، کنجکٹو گرائمرز ایک واحد نان ٹرمینل علامت کے لیے متعدد اصولوں کی نمائندگی کرنے والے مضمر اختلاط کی اجازت دیتے ہیں، جو سیاق و سباق سے پاک گرائمرز میں ظاہر ہونے والا واحد منطقی کنیکٹو ہے۔ کنجنکشن کا استعمال، خاص طور پر، زبانوں کے انٹرسیکشن کی وضاحت کے لیے کیا جا سکتا ہے۔ کنجکٹو گرائمرز کی مزید توسیع جسے بولین گرائمرز کہا جاتا ہے اضافی طور پر واضح نفی کی اجازت دیتا ہے۔ کنجکٹو گرامر کے اصول اس شکل کے ہوتے ہیں جہاں ایک نان ٹرمینل ہوتا ہے اور،..، اور میں علامتوں سے بنے تار ہوتے ہیں (بالترتیب ٹرمینل اور نان ٹرمینل علامتوں کے محدود سیٹ)۔ غیر رسمی طور پر، اس طرح کا ایک قاعدہ اس بات پر زور دیتا ہے کہ اس پر موجود ہر سٹرنگ جس کی نمائندگی کرتا ہے،..، اس لیے اس کی طرف سے بیان کردہ شرط کو پورا کرتا ہے۔ رسمی تعریف ایک مشترکہ گرائمر کی تعریف 4-ٹپل سے کی جاتی ہے جہاں ایک محدود سیٹ ہوتا ہے۔ ہر عنصر کو نان ٹرمینل علامت یا متغیر کہا جاتا ہے۔ ہر متغیر جملے میں ایک مختلف قسم کے جملے یا شق کی نمائندگی کرتا ہے۔ متغیرات کو بعض اوقات نحو زمرہ جات بھی کہا جاتا ہے۔ ٹرمینلز کا ایک محدود مجموعہ ہے، جو اس سے جدا ہوتے ہیں، جو جملے کا اصل مواد بناتے ہیں۔ ٹرمینلز کا مجموعہ زبان کا حروف تہجی ہے جس کی وضاحت گرائمر کے ذریعہ کی جاتی ہے۔ پروڈکشن کا ایک محدود مجموعہ ہے، اور میں کچھ کے لیے ہر ایک شکل۔ کے اراکین کو قواعد یا گرائمر کی پیداوار کہا جاتا ہے۔ اسٹارٹ متغیر (یا اسٹارٹ علامت) ہے، جو پورے جملے (یا پروگرام) کی نمائندگی کے لیے استعمال ہوتا ہے۔ یہ ایک عنصر ہونا چاہیے۔ ایک ہی لائن پر ایک ہی بائیں ہاتھ کی طرف کے تمام دائیں ہاتھ کے اطراف کی فہرست بنانا عام بات ہے، انہیں الگ کرنے کے لیے | (پائپ کی علامت) کا استعمال کرتے ہوئے۔ قواعد اور اس لیے اس طرح لکھے جا سکتے ہیں۔ مشترکہ گرائمر کے ذریعہ مخصوص زبان کی دو مساوی رسمی تعریفیں موجود ہیں۔ ایک تعریف گرائمر کو یونین، انٹرسیکشن اور کنکیٹی نیشن کے ساتھ زبان کی مساوات کے نظام کے طور پر پیش کرنے اور اس کے سب سے کم حل پر غور کرنے پر مبنی ہے۔ دوسری تعریف چومسکی کی سیاق و سباق سے پاک گرائمر کی جنریٹو تعریف کو عام کرتی ہے جس میں کنجکشن اور کنکٹی نیشن پر اصطلاحات کی دوبارہ تحریر کا استعمال کیا گیا ہے۔ مشتق کے ذریعہ تعریف کسی بھی سٹرنگ کے لیے، ہم کہتے ہیں کہ براہ راست پیداوار ہوتی ہے، اس طرح لکھا جاتا ہے، اگر یا تو کوئی قاعدہ موجود ہے اور، یا اس طرح کی سٹرنگ موجود ہے کہ اور۔ کسی بھی سٹرنگ کے لیے ہم کہتے ہیں کہ اس طرح لکھا جاتا ہے، اگر ایسا ہے۔ گرامر کی زبان ان تمام تاروں کا مجموعہ ہے جو اس سے پیدا ہوتے ہیں۔ مثال گرائمر، پروڈکشن کے ساتھ،،،،، مشترکہ ہے۔ ایک عام مشتق یہ ہے کہ یہ دکھایا جا سکتا ہے۔ زبان سیاق و سباق سے پاک نہیں ہے، سیاق و سباق سے پاک زبانوں کے لیے پمپنگ لیما سے ثابت ہوتی ہے۔ اگرچہ کنجکٹو گرائمرز کی اظہار کی طاقت سیاق و سباق سے پاک گرائمرز سے زیادہ ہے، لیکن کنجکٹو گرائمرز مؤخر الذکر میں سے کچھ کو برقرار رکھتے ہیں۔ سب سے اہم بات یہ ہے کہ اہم سیاق و سباق سے پاک تجزیہ الگورتھم کی عمومییاں موجود ہیں، جن میں لکیری ٹائم ریکرسو ڈیسنٹ، کیوبک ٹائم جنرلائزڈ ایل آر، کیوبک ٹائم کاک-کسامی-ینگ کے ساتھ ساتھ ویلینٹ کا الگورتھم بھی شامل ہے جو میٹرکس ضرب کی طرح تیزی سے چل رہا ہے۔ نظریاتی خصوصیات ایک ایسی خاصیت جو سیاق و سباق سے پاک زبانوں یا ان کے محدود چوراہوں کے لیے پہلے سے ہی ناقابل فیصلہ ہے، مشترکہ گرامر کے لیے بھی ناقابل فیصلہ ہونا چاہیے۔ ان میں شامل ہیں: خالی پن، حد، باقاعدگی، سیاق و سباق کی آزادی، شمولیت اور مساوات۔ کنجکٹو زبانوں کا خاندان یونین، انٹرسیکشن، کنکیٹی نیشن اور کلین اسٹار کے تحت بند ہے، لیکن سٹرنگ ہومومورفزم، پریفیکس، لاحقہ اور سبسٹرنگ کے تحت نہیں۔ تکمیل کے تحت اور ε-فری سٹرنگ ہومومورفزم کے تحت بندش اب بھی کھلے مسائل ہیں (2001 تک)۔ ایک حرفی حروف تہجی پر گرائمر کی اظہار کی طاقت پر تحقیق کی گئی ہے۔ اس کام نے زیادہ عمومی شکل کی زبان کی مساوات کے مطالعہ کے لیے ایک بنیاد فراہم کی۔ مطابقت پذیر متبادل پش ڈاؤن آٹومیٹا ایزکووٹز اور کامنسکی نے پش ڈاؤن آٹومیٹا (پی ڈی اے) کی ایک نئی کلاس متعارف کرائی جسے مطابقت پذیر متبادل پش ڈاؤن آٹومیٹا (ایس اے پی ڈی اے) کہا جاتا ہے۔ انہوں نے اسے مشترکہ گرائمرز کے مساوی ثابت کیا جس طرح غیر متعین پی ڈی اے سیاق و سباق سے پاک گرائمرز کے مساوی ہیں۔ نوٹ حوالہ جات بیرونی روابط تکنیکی رپورٹ ورژن (پی ڈی ایف) رسمی زبانیں