۰
subtitle
ارسال: #۱
تبدیل DFA به DFA بهینه
سلام دوستان
با توجه به اینکه باید یک DFA داده شده را به DFA بهینه تبدیل کرد و امکان دارد در DFA داده شده Dead state وجود داشته باشد . من به مشکلی برخوردم که Dead state را چگونه می توان حذف کرد ؟ ایا قانون خاصی دارد ؟ مثال هم پیدا نکردم که درست توضیح داده شده باشد ؟
انگار که بر حسب ذهن این کار رو می کنن .
آیا این همان حالت دامی می باشد در نظریه زبان ها ؟
تشکر
با توجه به اینکه باید یک DFA داده شده را به DFA بهینه تبدیل کرد و امکان دارد در DFA داده شده Dead state وجود داشته باشد . من به مشکلی برخوردم که Dead state را چگونه می توان حذف کرد ؟ ایا قانون خاصی دارد ؟ مثال هم پیدا نکردم که درست توضیح داده شده باشد ؟
انگار که بر حسب ذهن این کار رو می کنن .
آیا این همان حالت دامی می باشد در نظریه زبان ها ؟
تشکر
۰
ارسال: #۲
RE: تبدیل DFA به DFA بهینه
(۳۰ آذر ۱۳۹۳ ۱۰:۲۶ ب.ظ)sadegh2013 نوشته شده توسط: سلام دوستان
با توجه به اینکه باید یک DFA داده شده را به DFA بهینه تبدیل کرد و امکان دارد در DFA داده شده Dead state وجود داشته باشد . من به مشکلی برخوردم که Dead state را چگونه می توان حذف کرد ؟ ایا قانون خاصی دارد ؟ مثال هم پیدا نکردم که درست توضیح داده شده باشد ؟
انگار که بر حسب ذهن این کار رو می کنن .
آیا این همان حالت دامی می باشد در نظریه زبان ها ؟
تشکر
سلام
ببینید DFA اول باید به صورت کامل باشه یعنی اینکه در هر حالت به ازای هر حرف الفبامون به یه حالتی بریم.(پس ممکنه حالت مرده وجود داشته باشه) و توی مینیمایز کردن اصن قرار نیس حالت مرده حذف شه و این که امکانش هست بعد مینیمایز کردن حالت مرده بوجود بیاد.
تنها چیزی که مهمه اینه که بعد مینیمایز سازی هیچ دو حالتی قابل ادغام نباشه.
ارسال: #۳
RE: تبدیل DFA به DFA بهینه
(۰۱ دى ۱۳۹۳ ۱۲:۰۹ ق.ظ)Imankhani نوشته شده توسط:(30 آذر ۱۳۹۳ ۱۰:۲۶ ب.ظ)sadegh2013 نوشته شده توسط: سلام دوستان
با توجه به اینکه باید یک DFA داده شده را به DFA بهینه تبدیل کرد و امکان دارد در DFA داده شده Dead state وجود داشته باشد . من به مشکلی برخوردم که Dead state را چگونه می توان حذف کرد ؟ ایا قانون خاصی دارد ؟ مثال هم پیدا نکردم که درست توضیح داده شده باشد ؟
انگار که بر حسب ذهن این کار رو می کنن .
آیا این همان حالت دامی می باشد در نظریه زبان ها ؟
تشکر
سلام
ببینید DFA اول باید به صورت کامل باشه یعنی اینکه در هر حالت به ازای هر حرف الفبامون به یه حالتی بریم.(پس ممکنه حالت مرده وجود داشته باشه) و توی مینیمایز کردن اصن قرار نیس حالت مرده حذف شه و این که امکانش هست بعد مینیمایز کردن حالت مرده بوجود بیاد.
تنها چیزی که مهمه اینه که بعد مینیمایز سازی هیچ دو حالتی قابل ادغام نباشه.
درست می فرمایید ولی سوال اینه هست که اصلا حذف dead state در چه جاهای صورت می گیرد و برای چه ؟
ارسال: #۴
RE: تبدیل DFA به DFA بهینه
دو نوع DFA داریم یا هر نوع ماشینه دیگه ای یکی اینه که کامل است یعنی اینکه ما به ازای هر حرف الفبا یه حالت میکشیم براش و نوع بعدی جزئی هست که حالت های مرده رسم نمیشه . پس جای مشخصی نداره که کجا حالت های مرده رسم نمیشه بستگی به رویکرد طراح دراه.
ارسال: #۶
RE: تبدیل DFA به DFA بهینه
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close