سلام
۱-آیا میتوان یک dfa که دارای چندین حالت نهایی هست رو به یک dfa که دارای یک حالت نهایی هست تبدیل کرد؟اگر بله چجوری؟
۲-آیا dfa میتونه چندین حالت شروع داشته باشه؟
۳-اگر جواب سوال۲ بله هست،آیا میتوان یک dfa که دارای چندین حالت شروع هست رو به یک dfa که فقط یک حالت شروع دارد تبدیل کرد؟به چه شکل؟
با سلام
نخیر هر DFA با چند حالت نهایی را نمیشه تبدیل کرد به یک DFA معادل فقط با یک حالت نهایی (دقت کنید گفتیم هر DFA یعنی برای تمام DFA ها صادق نیست این جمله) اما ممکنه DFA باشه که چندتا حالت نهایی داره اما بشه براش یک DFA با تنها یک جالت نهایی کشید (مثلا ممکنه کمینه اش کنید و تبدیل بشه به یک DFA با یک حالت نهایی) اینم به خاطر اینه که برای یک زبان شما بی نهایت ماشین می تونی بکشی
در مورد سوال دوم نخیر DFA نمی تونه چندتا حالت شروع داشته باشه و باید یک حالت شروع داشته باشه موفق باشید
(۰۶ بهمن ۱۳۹۳ ۰۶:۵۲ ب.ظ)Hamid_0311 نوشته شده توسط: با سلام
نخیر هر DFA با چند حالت نهایی را نمیشه تبدیل کرد به یک DFA معادل فقط با یک حالت نهایی (دقت کنید گفتیم هر DFA یعنی برای تمام DFA ها صادق نیست این جمله) اما ممکنه DFA باشه که چندتا حالت نهایی داره اما بشه براش یک DFA با تنها یک جالت نهایی کشید (مثلا ممکنه کمینه اش کنید و تبدیل بشه به یک DFA با یک حالت نهایی) اینم به خاطر اینه که برای یک زبان شما بی نهایت ماشین می تونی بکشی
در مورد سوال دوم نخیر DFA نمی تونه چندتا حالت شروع داشته باشه و باید یک حالت شروع داشته باشه موفق باشید
مرسی
