Parikh's theorem
نظریاتی کمپیوٹر سائنس میں پریکھ کا نظریہ کہتا ہے کہ اگر کوئی صرف سیاق و سباق سے پاک زبان میں ہر آخری علامت کے واقعات کی تعداد کو دیکھتا ہے، ان کی ترتیب کی پرواہ کیے بغیر، تو وہ زبان باقاعدہ زبان سے ناقابل شناخت ہے۔ یہ فیصلہ کرنے کے لیے مفید ہے کہ دی گئی تعداد میں ٹرمینلز والے تار سیاق و سباق سے پاک گرائمر کے ذریعے قبول نہیں کیے جاتے ہیں۔ اسے پہلی بار روہت پاریکھ نے 1961 میں ثابت کیا اور 1966 میں دوبارہ شائع کیا گیا۔ تعریفیں اور رسمی بیان حروف تہجی ہونے دیں۔ کسی لفظ کے پریکھ ویکٹر کی تعریف اس فنکشن کے طور پر کی جاتی ہے، جس کے ذریعے لفظ میں موجود حرف کے واقعات کی تعداد کو ظاہر کیا جاتا ہے۔ کے ذیلی سیٹ کو لکیری کہا جاتا ہے اگر یہ کچھ ویکٹروں کی شکل کا ہو۔ کے ذیلی سیٹ کو نیم لکیری کہا جاتا ہے اگر یہ محدود طور پر بہت سے لکیری ذیلی سیٹوں کا اتحاد ہو۔ مختصرا، سیاق و سباق سے پاک زبانوں اور باقاعدہ زبانوں کی تصویر ایک جیسی ہے، اور یہ نیم لکیری سیٹوں کے سیٹ کے برابر ہے۔ دو زبانوں کو باہمی طور پر مساوی کہا جاتا ہے اگر ان میں پریکھ ویکٹر کا ایک ہی مجموعہ ہو۔ اس طرح، ہر سیاق و سباق سے پاک زبان تبادلے کے لحاظ سے کسی باقاعدہ زبان کے مساوی ہے۔ ثبوت دوسرے حصے کو ثابت کرنا آسان ہے۔ پہلا حصہ کم آسان ہے۔ مندرجہ ذیل ثبوت کا سہرا گولڈسٹائن کو جاتا ہے۔ سب سے پہلے ہمیں سیاق و سباق سے پاک زبانوں کے لیے پمپنگ لیما کی ایک چھوٹی سی مضبوطی کی ضرورت ہے: ثبوت بنیادی طور پر معیاری پمپنگ لیما جیسا ہی ہے: کبوتر کے سوراخ کے اصول کا استعمال کرتے ہوئے مختصر ترین مشتق درخت میں طویل ترین راستے میں کچھ غیر آخری علامت کی کاپیاں تلاش کریں۔ باؤنڈڈ زبانوں کے لیے مضبوطی ایک زبان باؤنڈڈ ہوتی ہے اگر کچھ فکسڈ الفاظ کے لیے۔ گنزبرگ اور اسپانیئر نے پابند زبانوں کے لیے، پریکھ کے نظریہ کی طرح، ایک ضروری اور کافی شرط دی۔ اگر اس کی تعریف میں ہر ایک ویکٹر کے لیے یہ خاصیت ہے کہ اس کے زیادہ سے زیادہ دو غیر صفر نقاط ہیں، اور ہر ایک کے لیے اگر ہر ایک ویکٹر کے دو غیر صفر نقاط ہیں، اور، بالترتیب، تو ان کی ترتیب نہیں ہے۔ ایک نیم لکیری سیٹ کو درجہ بند کیا جاتا ہے اگر یہ محدود طور پر بہت سے درجہ بند لکیری ذیلی سیٹوں کا اتحاد ہو۔ اہمیت نظریہ کی متعدد تشریحات ہیں۔ اس سے پتہ چلتا ہے کہ سنگلٹن حروف تہجی پر سیاق و سباق سے پاک زبان ایک باقاعدہ زبان ہونی چاہیے اور یہ کہ کچھ سیاق و سباق سے پاک زبانوں میں صرف مبہم گرائمر ہو سکتے ہیں۔ ایسی زبانوں کو فطری طور پر مبہم زبانیں کہا جاتا ہے۔ رسمی گرائمر کے نقطہ نظر سے، اس کا مطلب ہے کہ کچھ مبہم سیاق و سباق سے پاک گرائمرز کو مساوی غیر واضح سیاق و سباق سے پاک گرائمرز میں تبدیل نہیں کیا جا سکتا۔ حوالہ جات رسمی زبانیں