تالار گفتمان مانشت

نسخه‌ی کامل: چند سوال درمورد تعداد حالات نهایی و شروع dfaها
شما در حال مشاهده‌ی نسخه‌ی متنی این صفحه می‌باشید. مشاهده‌ی نسخه‌ی کامل با قالب بندی مناسب.
سلام

1-آیا میتوان یک dfa که دارای چندین حالت نهایی هست رو به یک dfa که دارای یک حالت نهایی هست تبدیل کرد؟اگر بله چجوری؟
2-آیا dfa میتونه چندین حالت شروع داشته باشه؟
3-اگر جواب سوال2 بله هست،آیا میتوان یک dfa که دارای چندین حالت شروع هست رو به یک dfa که فقط یک حالت شروع دارد تبدیل کرد؟به چه شکل؟
با سلام
نخیر هر DFA با چند حالت نهایی را نمیشه تبدیل کرد به یک DFA معادل فقط با یک حالت نهایی (دقت کنید گفتیم هر DFA یعنی برای تمام DFA ها صادق نیست این جمله) اما ممکنه DFA باشه که چندتا حالت نهایی داره اما بشه براش یک DFA با تنها یک جالت نهایی کشید (مثلا ممکنه کمینه اش کنید و تبدیل بشه به یک DFA با یک حالت نهایی) اینم به خاطر اینه که برای یک زبان شما بی نهایت ماشین می تونی بکشی

در مورد سوال دوم نخیر DFA نمی تونه چندتا حالت شروع داشته باشه و باید یک حالت شروع داشته باشه موفق باشید
(06 بهمن 1393 06:52 ب.ظ)Hamid_0311 نوشته شده توسط: [ -> ]با سلام
نخیر هر DFA با چند حالت نهایی را نمیشه تبدیل کرد به یک DFA معادل فقط با یک حالت نهایی (دقت کنید گفتیم هر DFA یعنی برای تمام DFA ها صادق نیست این جمله) اما ممکنه DFA باشه که چندتا حالت نهایی داره اما بشه براش یک DFA با تنها یک جالت نهایی کشید (مثلا ممکنه کمینه اش کنید و تبدیل بشه به یک DFA با یک حالت نهایی) اینم به خاطر اینه که برای یک زبان شما بی نهایت ماشین می تونی بکشی

در مورد سوال دوم نخیر DFA نمی تونه چندتا حالت شروع داشته باشه و باید یک حالت شروع داشته باشه موفق باشید

مرسیSmile
لینک مرجع