سلام دوستان
با توجه به اینکه باید یک DFA داده شده را به DFA بهینه تبدیل کرد و امکان دارد در DFA داده شده Dead state وجود داشته باشد . من به مشکلی برخوردم که Dead state را چگونه می توان حذف کرد ؟ ایا قانون خاصی دارد ؟ مثال هم پیدا نکردم که درست توضیح داده شده باشد ؟
انگار که بر حسب ذهن این کار رو می کنن .
آیا این همان حالت دامی می باشد در نظریه زبان ها ؟
تشکر
(۳۰ آذر ۱۳۹۳ ۱۰:۲۶ ب.ظ)sadegh2013 نوشته شده توسط: سلام دوستان
با توجه به اینکه باید یک DFA داده شده را به DFA بهینه تبدیل کرد و امکان دارد در DFA داده شده Dead state وجود داشته باشد . من به مشکلی برخوردم که Dead state را چگونه می توان حذف کرد ؟ ایا قانون خاصی دارد ؟ مثال هم پیدا نکردم که درست توضیح داده شده باشد ؟
انگار که بر حسب ذهن این کار رو می کنن .
آیا این همان حالت دامی می باشد در نظریه زبان ها ؟
تشکر
سلام
ببینید DFA اول باید به صورت کامل باشه یعنی اینکه در هر حالت به ازای هر حرف الفبامون به یه حالتی بریم.(پس ممکنه حالت مرده وجود داشته باشه) و توی مینیمایز کردن اصن قرار نیس حالت مرده حذف شه و این که امکانش هست بعد مینیمایز کردن حالت مرده بوجود بیاد.
تنها چیزی که مهمه اینه که بعد مینیمایز سازی هیچ دو حالتی قابل ادغام نباشه.
(۰۱ دى ۱۳۹۳ ۱۲:۰۹ ق.ظ)Imankhani نوشته شده توسط:(30 آذر ۱۳۹۳ ۱۰:۲۶ ب.ظ)sadegh2013 نوشته شده توسط: سلام دوستان
با توجه به اینکه باید یک DFA داده شده را به DFA بهینه تبدیل کرد و امکان دارد در DFA داده شده Dead state وجود داشته باشد . من به مشکلی برخوردم که Dead state را چگونه می توان حذف کرد ؟ ایا قانون خاصی دارد ؟ مثال هم پیدا نکردم که درست توضیح داده شده باشد ؟
انگار که بر حسب ذهن این کار رو می کنن .
آیا این همان حالت دامی می باشد در نظریه زبان ها ؟
تشکر
سلام
ببینید DFA اول باید به صورت کامل باشه یعنی اینکه در هر حالت به ازای هر حرف الفبامون به یه حالتی بریم.(پس ممکنه حالت مرده وجود داشته باشه) و توی مینیمایز کردن اصن قرار نیس حالت مرده حذف شه و این که امکانش هست بعد مینیمایز کردن حالت مرده بوجود بیاد.
تنها چیزی که مهمه اینه که بعد مینیمایز سازی هیچ دو حالتی قابل ادغام نباشه.
درست می فرمایید ولی سوال اینه هست که اصلا حذف dead state در چه جاهای صورت می گیرد و برای چه ؟
دو نوع DFA داریم یا هر نوع ماشینه دیگه ای یکی اینه که کامل است یعنی اینکه ما به ازای هر حرف الفبا یه حالت میکشیم براش و نوع بعدی جزئی هست که حالت های مرده رسم نمیشه . پس جای مشخصی نداره که کجا حالت های مرده رسم نمیشه بستگی به رویکرد طراح دراه.
آیا این همان حالت دامی هست ؟
(۰۱ دى ۱۳۹۳ ۱۰:۳۶ ب.ظ)sadegh2013 نوشته شده توسط: آیا این همان حالت دامی هست ؟
فک کنم دامی هم بهش بگن. ولی بیشتر dead state استفاده میشه.