زبانوں کا چومسکی درجہ بندی کیا ہے اور یہ ان کی تخلیقی طاقت کی بنیاد پر رسمی گرامر کی درجہ بندی کیسے کرتی ہے؟
زبانوں کا چومسکی درجہ بندی ایک درجہ بندی کا نظام ہے جو رسمی گرامر کو ان کی تخلیقی طاقت کی بنیاد پر درجہ بندی کرتا ہے۔ اسے 1950 کی دہائی میں معروف ماہر لسانیات اور کمپیوٹر سائنس دان نوم چومسکی نے تجویز کیا تھا۔ درجہ بندی چار سطحوں پر مشتمل ہے، ہر ایک رسمی زبانوں کے مختلف طبقے کی نمائندگی کرتا ہے۔ ان سطحوں کو Type-3 (Regular)، Type-2 (Context-free)، Type-1 (Context-Sensitive)، اور Type-0 (غیر محدود) کے نام سے جانا جاتا ہے۔
درجہ بندی کی نچلی سطح پر، ہمارے پاس Type-3 زبانیں ہیں، جنہیں باقاعدہ زبانیں بھی کہا جاتا ہے۔ ان زبانوں کو محدود آٹومیٹا کے ذریعے پہچانا جا سکتا ہے، جیسے ڈیٹرمینسٹک اور نان ڈیٹرمنسٹک فائنائٹ آٹو میٹا۔ باقاعدہ زبانیں باقاعدہ اظہار اور باقاعدہ گرامر کی خصوصیت رکھتی ہیں۔ ریگولر ایکسپریشنز الجبری ایکسپریشنز ہیں جو سٹرنگز کے پیٹرن کو بیان کرتے ہیں، جبکہ ریگولر گرائمر پروڈکشن رولز پر مشتمل ہوتے ہیں جو ایک باقاعدہ زبان میں ڈور تیار کرتے ہیں۔ ایک ریگولر لینگوئج کی ایک مثال تمام سٹرنگز کا سیٹ ہے جو ایک دیے گئے ریگولر ایکسپریشن سے میل کھاتا ہے، جیسے کہ تمام بائنری سٹرنگز کی لینگویج 0s کی یکساں تعداد کے ساتھ۔
درجہ بندی کو آگے بڑھاتے ہوئے، ہمیں Type-2 زبانوں کا سامنا کرنا پڑتا ہے، جنہیں سیاق و سباق سے پاک زبانیں بھی کہا جاتا ہے۔ ان زبانوں کو پش ڈاون آٹومیٹا کے ذریعے پہچانا جا سکتا ہے، جو کہ ایک اسٹیک کے ساتھ بڑھا ہوا محدود آٹو میٹا ہے۔ سیاق و سباق سے پاک زبانوں کو سیاق و سباق سے پاک گرامر کے ذریعے بیان کیا جاتا ہے، جو کہ پیداواری اصولوں پر مشتمل ہوتے ہیں جو سیاق و سباق سے پاک زبان میں تار تیار کرتے ہیں۔ سیاق و سباق سے پاک گرامر میں غیر ٹرمینل علامتیں، ٹرمینل علامتیں، اور پیداواری اصول ہوتے ہیں جو یہ بتاتے ہیں کہ غیر ٹرمینلز کو علامتوں کی ترتیب سے کیسے بدلا جا سکتا ہے۔ سیاق و سباق سے پاک زبان کی ایک مثال تمام اچھی طرح سے بنائے گئے ریاضی کے تاثرات کا مجموعہ ہے، جہاں قوسین متوازن ہوتے ہیں اور آپریٹرز کو درست طریقے سے لاگو کیا جاتا ہے۔
درجہ بندی کی اگلی سطح Type-1 زبانیں ہیں، جنہیں سیاق و سباق سے متعلق حساس زبانیں بھی کہا جاتا ہے۔ ان زبانوں کو لکیری باؤنڈڈ آٹومیٹا کے ذریعے پہچانا جا سکتا ہے، جو ایک ٹیپ کے ساتھ محدود آٹومیٹا ہیں جو دونوں سمتوں میں حرکت کر سکتی ہیں۔ سیاق و سباق سے متعلق حساس زبانوں کو سیاق و سباق سے حساس گرامر کے ذریعہ بیان کیا جاتا ہے، جو پیداواری اصولوں پر مشتمل ہوتے ہیں جو سیاق و سباق کے لحاظ سے حساس زبان میں تار تیار کرتے ہیں۔ سیاق و سباق کے لحاظ سے حساس گرامر میں یہ اضافی پابندی ہے کہ پیداواری اصول کے دائیں ہاتھ کی لمبائی بائیں ہاتھ کی لمبائی سے کم نہیں ہوسکتی ہے۔ سیاق و سباق سے متعلق حساس زبان کی ایک مثال تمام پیلینڈروم کا مجموعہ ہے، جہاں ایک تار ایک ہی آگے اور پیچھے پڑھتا ہے۔
آخر میں، درجہ بندی کے سب سے اوپر، ہمارے پاس Type-0 زبانیں ہیں، جنہیں غیر محدود زبانیں بھی کہا جاتا ہے۔ ان زبانوں کو ٹورنگ مشینوں کے ذریعے پہچانا جا سکتا ہے، جو کہ کسی بھی کمپیوٹر الگورتھم کی نقل کرنے کے قابل تجریدی کمپیوٹیشنل ڈیوائسز ہیں۔ غیر محدود زبانیں غیر محدود گرامر کے ذریعہ بیان کی جاتی ہیں، جن پر پیداواری قواعد کی کوئی پابندی نہیں ہے۔ غیر محدود زبان کی ایک مثال تمام تکراری گنتی زبانوں کا مجموعہ ہے، جس میں تمام کمپیوٹیبل زبانیں شامل ہیں۔
زبانوں کا چومسکی درجہ بندی ان کی تخلیقی طاقت کی بنیاد پر رسمی گرامر کی درجہ بندی کے لیے ایک منظم فریم ورک فراہم کرتا ہے۔ یہ باقاعدہ زبانوں سے شروع ہوتی ہے، جو کم سے کم طاقتور ہوتی ہیں، اور سیاق و سباق سے پاک، سیاق و سباق سے حساس، اور غیر محدود زبانوں میں ترقی کرتی ہیں، جو تیزی سے زیادہ طاقتور ہوتی جا رہی ہیں۔ یہ درجہ بندی کمپیوٹیشنل پیچیدگی تھیوری کے میدان میں ایک بنیادی تصور ہے اور رسمی زبانوں اور آٹو میٹا کے مطالعہ کے لیے اس کے اہم مضمرات ہیں۔
سے متعلق دیگر حالیہ سوالات اور جوابات چومسکی درجہ بندی اور سیاق و سباق سے متعلق حساس زبانیں:
- اس کا کیا مطلب ہے کہ ایک زبان دوسری زبان سے زیادہ طاقتور ہے؟
- کیا ٹائپ 0 کو پہچاننے کے موجودہ طریقے ہیں؟ کیا ہم توقع کرتے ہیں کہ کوانٹم کمپیوٹرز اسے قابل عمل بنائیں گے؟
- ایک زبان کے لیے سیاق و سباق کے لحاظ سے حساس گرائمر کو ڈیزائن کرنے کے عمل کی وضاحت کریں جس میں ایک، دو اور تین کی تعداد کے ساتھ تار شامل ہوں۔
- سیاق و سباق کے لحاظ سے حساس زبان کی مثال دیں اور وضاحت کریں کہ اسے سیاق و سباق کے لحاظ سے حساس گرامر سے کیسے پہچانا جا سکتا ہے۔
- ٹائپ 0 زبانیں، جنہیں بار بار گنتی کی جانے والی زبانیں بھی کہا جاتا ہے، کمپیوٹیشنل پیچیدگی کے لحاظ سے دوسری قسم کی زبانوں سے کیسے مختلف ہیں؟
- سیاق و سباق سے پاک زبانوں اور سیاق و سباق کے لحاظ سے حساس زبانوں کے درمیان فرق کی وضاحت ان قواعد کے لحاظ سے کریں جو ان کی تشکیل کو کنٹرول کرتے ہیں۔