جب ہمارے پاس غیر متعین مشین میں دو یا زیادہ قابل قبول راستے ہوتے ہیں، تو ہم کون سا انتخاب کرتے ہیں اور ہم کون سا معیار استعمال کر سکتے ہیں؟
کمپیوٹیشنل پیچیدگی کے نظریہ کے دائرے میں، خاص طور پر محدود ریاستی مشینوں کے مطالعہ میں، عدم تعین کا تصور ایک اہم کردار ادا کرتا ہے۔
نان ڈیٹرمنسٹک فائنیٹ سٹیٹ مشینیں (NFSMs) نظریاتی ماڈل ہیں جو کسی بھی ریاست میں متعدد قابل قبول راستے اختیار کرنے کی اجازت دیتے ہیں۔ تاہم جب ایسی صورت حال کا سامنا ہو تو سوال یہ پیدا ہوتا ہے کہ کون سا راستہ چنا جائے؟
یہ استفسار NFSMs میں "قبولیت" کے تصور اور فیصلہ کرنے کے لیے استعمال کیے جانے والے معیار پر ہے۔
انتخاب کے عمل کو سمجھنے کے لیے، آئیے پہلے NFSMs میں عدم استحکام کی نوعیت کو دریافت کریں۔ deterministic finite state machines (DFSMs) کے برعکس، NFSMs ہر ریاست میں ہر ممکنہ ان پٹ علامت کے لیے منفرد منتقلی کے مالک نہیں ہوتے ہیں۔ اس کے بجائے، وہ ایک ہی ان پٹ علامت کے لیے متعدد ٹرانزیشنز کے وجود کی اجازت دیتے ہیں۔ یہ خصوصیت ایک ہی ریاست سے متعدد راستوں پر چلنے کے امکان کی طرف لے جاتی ہے، جس کے نتیجے میں ممکنہ طور پر مختلف نتائج برآمد ہوتے ہیں۔
جب ایسی صورت حال کا سامنا ہوتا ہے، NFSMs ایک طریقہ کار استعمال کرتے ہیں جسے "برانچنگ" کہا جاتا ہے تاکہ بیک وقت تمام ممکنہ راستوں کو تلاش کیا جا سکے۔ اس کا مطلب یہ ہے کہ مشین خود کی متعدد کاپیاں بناتی ہے، ہر ایک مختلف راستے پر چلتی ہے۔ نتیجے کے طور پر، NFSM کو درخت نما ڈھانچے کی تلاش کے طور پر دیکھا جا سکتا ہے، جہاں ہر شاخ مختلف حسابی راستے کی نمائندگی کرتی ہے۔ یہ برانچنگ تکنیک NFSMs اور ان کی کمپیوٹیشنل پیچیدگی کے تجزیہ میں بنیادی ہے۔
اب، آئیے ان معیارات پر غور کریں جن کو متعدد قابل قبول لوگوں میں سے ایک مخصوص راستہ منتخب کرنے کے لیے استعمال کیا جا سکتا ہے۔ ایک عام نقطہ نظر NFSMs میں "قبولیت" کے تصور پر غور کرنا ہے۔ قبولیت سے مراد وہ شرط ہے جو اس بات کا تعین کرتی ہے کہ آیا دیا گیا ان پٹ مشین کے ذریعہ درست سمجھا جاتا ہے یا نہیں۔ NFSMs میں، قبولیت کی تعریف دو اہم طریقوں سے کی جا سکتی ہے: "حتمی حالت کے ذریعے قبولیت" اور "خالی اسٹیک کے ذریعے قبولیت۔"
حتمی حالت کی طرف سے قبولیت اس وقت ہوتی ہے جب، پوری ان پٹ سٹرنگ استعمال کرنے پر، NFSM ایک حتمی حالت کے طور پر نامزد ریاست میں ختم ہو جاتا ہے۔ اس معیار کا مطلب یہ ہے کہ مشین ان پٹ کو قبول کرتی ہے اگر کم از کم ایک حسابی راستہ موجود ہے جو حتمی حالت کی طرف لے جاتا ہے۔ اس کے برعکس، اگر کوئی راستہ حتمی حالت کی طرف نہیں جاتا ہے، تو ان پٹ کو مسترد کر دیا جاتا ہے۔
دوسری طرف، خالی اسٹیک کے ذریعے قبولیت اس وقت متعلقہ ہوتی ہے جب NFSMs اسٹیک کو ایک اضافی جزو کے طور پر شامل کرتے ہیں۔ اس منظر نامے میں، قبولیت اس وقت ہوتی ہے جب ان پٹ سٹرنگ مکمل طور پر پروسیس ہو جاتی ہے، اور اسٹیک خالی ہو جاتا ہے۔ حتمی حالت کی طرف سے قبولیت کی طرح، اگر کم از کم ایک حسابی راستہ موجود ہے جس کے نتیجے میں خالی اسٹیک ہوتا ہے، ان پٹ کو قبول کیا جاتا ہے؛ دوسری صورت میں، یہ مسترد کر دیا جاتا ہے.
ان معیارات کو دیکھتے ہوئے، ایک غیر مقررہ مشین میں متعدد قابل قبول راستوں کے درمیان ایک مخصوص راستے کا انتخاب قبولیت کی شرائط کو ترجیح دے کر طے کیا جا سکتا ہے۔ مثال کے طور پر، اگر حتمی حالت کی طرف سے قبولیت بنیادی معیار ہے، تو مشین دوسرے ممکنہ راستوں سے قطع نظر، حتمی حالت کی طرف لے جانے والے راستے کا انتخاب کرے گی۔ اس کے برعکس، اگر خالی اسٹیک کے ذریعہ قبولیت بنیادی معیار ہے، تو مشین اس راستے کو ترجیح دے گی جس کے نتیجے میں خالی اسٹیک ہوتا ہے۔
یہ نوٹ کرنا ضروری ہے کہ NFSMs میں راستے کا انتخاب مشین کی کمپیوٹیشنل طاقت کو متاثر نہیں کرتا ہے۔ منتخب کردہ راستے سے قطع نظر، NFSM پھر بھی زبانوں کے ایک ہی سیٹ کو تسلیم کر سکتا ہے جیسے کسی دوسرے NFSM کو دیے گئے ان پٹ کے لیے۔ انتخاب کا عمل صرف مخصوص معیار کی بنیاد پر ان پٹ کی قبولیت یا مسترد ہونے کا تعین کرتا ہے۔
جب ایک غیر متعین مشین میں متعدد قابل قبول راستوں کا سامنا کرنا پڑتا ہے، تو راستے کے انتخاب کا تعین قبولیت کی شرائط کو ترجیح دے کر کیا جا سکتا ہے، جیسے کہ حتمی حالت کے ذریعے قبولیت یا خالی اسٹیک کے ذریعے قبولیت۔ انتخاب کا عمل مشین کی کمپیوٹیشنل طاقت کو متاثر نہیں کرتا بلکہ اس پر اثر انداز ہوتا ہے کہ آیا ان پٹ کو قبول کیا گیا ہے یا مسترد کیا گیا ہے۔
سے متعلق دیگر حالیہ سوالات اور جوابات EITC/IS/CCTF کمپیوٹیشنل کمپلیکسٹی تھیوری کے بنیادی اصول:
- کمپیوٹیشنل پیچیدگی تھیوری فارملزم کی تفہیم کے لیے کچھ بنیادی ریاضیاتی تعریفیں، اشارے اور تعارف کی کیا ضرورت ہے؟
- خفیہ نگاری اور سائبرسیکیوریٹی کی بنیادوں کو سمجھنے کے لیے کمپیوٹیشنل پیچیدگی کا نظریہ کیوں اہم ہے؟
- اے ٹی ایم کی غیر فیصلہ کنیت کے مظاہرے میں تکرار نظریہ کا کیا کردار ہے؟
- پی ڈی اے پر غور کرتے ہوئے جو پیلینڈروم کو پڑھ سکتا ہے، کیا آپ اسٹیک کے ارتقاء کی تفصیل بتا سکتے ہیں جب ان پٹ، پہلا، پیلینڈروم، اور دوسرا، پیلینڈروم نہیں ہے؟
- غیر متعین PDAs پر غور کرتے ہوئے، تعریف کے لحاظ سے ریاستوں کی سپر پوزیشن ممکن ہے۔ تاہم، غیر متعین PDAs میں صرف ایک اسٹیک ہوتا ہے جو بیک وقت متعدد ریاستوں میں نہیں ہو سکتا۔ یہ کیسے ممکن ہے؟
- نیٹ ورک ٹریفک کا تجزیہ کرنے اور ممکنہ حفاظتی خلاف ورزیوں کی نشاندہی کرنے والے نمونوں کی شناخت کے لیے استعمال ہونے والے PDAs کی کیا مثال ہے؟
- اس کا کیا مطلب ہے کہ ایک زبان دوسری زبان سے زیادہ طاقتور ہے؟
- کیا سیاق و سباق سے متعلق حساس زبانیں ٹورنگ مشین کے ذریعے پہچانی جا سکتی ہیں؟
- زبان U = 0^n1^n (n>=0) غیر باقاعدہ کیوں ہے؟
- '1' علامتوں کی یکساں تعداد کے ساتھ بائنری سٹرنگز کو پہچاننے والے FSM کی وضاحت کیسے کریں اور ان پٹ سٹرنگ 1011 پر کارروائی کرتے وقت اس کے ساتھ کیا ہوتا ہے؟
EITC/IS/CCTF کمپیوٹیشنل کمپلیکسٹی تھیوری کے بنیادی اصولوں میں مزید سوالات اور جوابات دیکھیں