deterministic اور nondeterministic محدود ریاستی مشینوں کے درمیان بنیادی فرق کیا ہے؟
ایک deterministic finite state machine (DFSM) اور ایک nondeterministic finite state machine (NFSM) دو قسم کی محدود ریاستی مشینیں (FSMs) ہیں جو کمپیوٹیشنل کمپلیکٹی تھیوری کے میدان میں استعمال ہوتی ہیں۔ اگرچہ دونوں FSMs میں ایک جیسی خصوصیات ہیں اور ان کا استعمال مختلف کمپیوٹیشنل پروسیسز کو ماڈل بنانے کے لیے کیا جا سکتا ہے، وہ اپنے رویے اور ان کی منتقلی کی نوعیت کے لحاظ سے مختلف ہیں۔
DFSM اور NFSM کے درمیان بنیادی فرق ریاستوں کے درمیان منتقلی کو سنبھالنے کے طریقے میں ہے۔ ڈی ایف ایس ایم میں، ایک حالت سے دوسری حالت میں منتقلی موجودہ حالت اور ان پٹ کی علامت سے منفرد طور پر طے کی جاتی ہے۔ اس کا مطلب یہ ہے کہ دی گئی ریاست اور ان پٹ علامت کے لیے، صرف ایک ہی ممکنہ اگلی حالت ہو سکتی ہے۔ دوسرے لفظوں میں، ڈی ایف ایس ایم ایک تعییناتی انداز میں کام کرتا ہے، جہاں اگلی حالت موجودہ حالت اور ان پٹ سے منفرد طور پر متعین ہوتی ہے۔
دوسری طرف، ایک NFSM ایک دی گئی ریاست اور ان پٹ علامت کے لیے متعدد ممکنہ اگلی ریاستوں کی اجازت دیتا ہے۔ اس کا مطلب یہ ہے کہ NFSM کے ٹرانزیشن فنکشن میں اگلی ریاست کے لیے متعدد درست انتخاب ہو سکتے ہیں۔ دوسرے لفظوں میں، NFSM غیر متعین انداز میں کام کرتا ہے، جہاں اگلی حالت موجودہ حالت اور ان پٹ سے منفرد طور پر متعین نہیں ہوتی ہے۔ اس کے بجائے، ایک NFSM بیک وقت ایک یا زیادہ ریاستوں میں منتقل ہو سکتا ہے، جس سے حساب کے متعدد ممکنہ راستے پیدا ہوتے ہیں۔
اس فرق کو واضح کرنے کے لیے، آئیے ایک مثال پر غور کریں۔ فرض کریں کہ ہمارے پاس ایک NFSM اور DFSM ہے جو دونوں ایک سادہ زبان کا نمونہ بناتے ہیں جو 0s اور 1s کے سٹرنگز کو قبول کرتی ہے جس کا اختتام 1 ہے۔ NFSM کی دو حالتیں ہیں: S0 اور S1۔ DFSM کی بھی دو حالتیں ہیں: Q0 اور Q1۔
NFSM کے لیے، اسٹیٹ S0 اور ان پٹ سمبل 0 کے لیے ٹرانزیشن فنکشن میں دو ممکنہ اگلی حالتیں ہو سکتی ہیں: S0 اور S1۔ اس کا مطلب یہ ہے کہ جب NFSM ریاست S0 میں ہے اور ان پٹ علامت 0 وصول کرتا ہے، تو یہ ریاست S0 یا ریاست S1 میں منتقل ہو سکتا ہے۔ دوسری طرف، اسٹیٹ S0 اور ان پٹ سمبل 1 کے لیے ٹرانزیشن فنکشن میں صرف ایک ہی ممکنہ اگلی حالت ہے: S1۔ اس کا مطلب یہ ہے کہ جب NFSM حالت S0 میں ہے اور اسے ان پٹ علامت 1 موصول ہوتا ہے، تو یہ ہمیشہ ریاست S1 میں منتقل ہو جائے گا۔
اس کے برعکس، DFSM کی موجودہ حالت اور ان پٹ علامت کے ہر امتزاج کے لیے ایک منفرد اگلی حالت ہے۔ مثال کے طور پر، جب DFSM حالت Q0 میں ہوتا ہے اور اسے ان پٹ علامت 0 موصول ہوتا ہے، تو یہ ہمیشہ Q0 حالت میں منتقل ہو جاتا ہے۔ اسی طرح، جب DFSM حالت Q0 میں ہوتا ہے اور اسے ان پٹ علامت 1 موصول ہوتا ہے، تو یہ ہمیشہ Q1 حالت میں منتقل ہو جاتا ہے۔
ڈیٹرمینسٹک اور نان ڈیٹرمینسٹک فائنیٹ سٹیٹ مشینوں کے درمیان بنیادی فرق ان کی ٹرانزیشن کی نوعیت میں ہے۔ ایک ڈیٹرمنسٹک فائنائٹ سٹیٹ مشین (DFSM) میں موجودہ حالت اور ان پٹ سمبل کے ہر امتزاج کے لیے ایک منفرد اگلی حالت ہوتی ہے، جب کہ ایک nondeterministic finite state machine (NFSM) موجودہ حالت اور ان پٹ سمبل کے دیے گئے امتزاج کے لیے متعدد ممکنہ اگلی ریاستوں کی اجازت دیتی ہے۔
سے متعلق دیگر حالیہ سوالات اور جوابات EITC/IS/CCTF کمپیوٹیشنل کمپلیکسٹی تھیوری کے بنیادی اصول:
- غیر متعین PDAs پر غور کرتے ہوئے، تعریف کے لحاظ سے ریاستوں کی سپر پوزیشن ممکن ہے۔ تاہم، غیر متعین PDAs میں صرف ایک اسٹیک ہوتا ہے جو بیک وقت متعدد ریاستوں میں نہیں ہو سکتا۔ یہ کیسے ممکن ہے؟
- کیا "نیٹ ورک ٹریفک کا تجزیہ کرنے اور ممکنہ حفاظتی خلاف ورزیوں کی نشاندہی کرنے والے نمونوں کی شناخت کے لیے" استعمال ہونے والے PDAs کی کوئی عملی مثال دے سکتے ہیں؟
- اس کا کیا مطلب ہے کہ ایک زبان دوسری زبان سے زیادہ طاقتور ہے؟
- کیا سیاق و سباق سے متعلق حساس زبانیں ٹورنگ مشین کے ذریعے پہچانی جا سکتی ہیں؟
- زبان U = 0^n1^n (n>=0) غیر باقاعدہ کیوں ہے؟
- '1' علامتوں کی یکساں تعداد کے ساتھ بائنری سٹرنگز کو پہچاننے والے FSM کی وضاحت کیسے کریں اور ان پٹ سٹرنگ 1011 پر کارروائی کرتے وقت اس کے ساتھ کیا ہوتا ہے؟
- نان ڈیٹرمنزم منتقلی کے کام کو کیسے متاثر کرتا ہے؟
- کیا باقاعدہ زبانیں Finite State Machines کے برابر ہیں؟
- کیا PSPACE کلاس EXPSPACE کلاس کے برابر نہیں ہے؟
- کیا الگورتھم کے لحاظ سے کمپیوٹیبل مسئلہ چرچ ٹورنگ تھیسس کے مطابق ٹیورنگ مشین کے ذریعہ شمار کیا جا سکتا ہے؟
EITC/IS/CCTF کمپیوٹیشنل کمپلیکسٹی تھیوری کے بنیادی اصولوں میں مزید سوالات اور جوابات دیکھیں