۱/آیا هر DFA را میتوان با یک DFA معادل با یک حالت نهایی و یک حالت شروع نمایش داد؟
۲/سوال بالا برای NFA.
برای NFA جواب هر دو بله است.چون با حرکات لاندا میتونیم تمام شروعها و همینطورتمام نهایی‌ها رو یکی کنیم.
ولی برای DFA فک کنم جواب یکیش باید بله بشه یعنی قبلا جایی خوندم اینو.
ولی نمیدونم کدومش و چه جوری؟
پاسخ شما دوست عزیز:
- برای هر NFA با چندین وضعیت نهایی، یک NFA معادل با فقط یک وضعیت نهایی وجود دارد . اما این حکم برای DFA صادق نیست( طبق کتاب لینز )
- برای هر DFA با چندین وضعیت ابتدایی، یک DFA معادل با فقط یک وضعیت ابتدایی وجود دارد . این حکم برای NFA هم صادق است( طبق کتاب لینز )
متشکرم parsaNA.
ببخشید من الان کتاب لینزم همرام نیست.
توی کتاب لینز ننوشته چه جوری حالات ابتدایی DFA رو یکی می کنیم؟
خودم حدس میزنم از راه تبدیل به NFA معادلش و حالات ابتدایی رو یکی کنیم تو NFA بعد اون رو تبدیل به DFA کنیم چون تو تبدیلش حالت اولیه همون حالت اولیه NFA هست پس یک حالت میشه.
اما برای حالت نهایی نمیتونیم این کار رو انجام بدیم چون چند تا حالت نهایی مختلف ممکنه تولید بشه در تبدیل.
میشه ببینید روشش همینجوری هست یا نه؟
به خاطر این روش رو میپرسم چون من نمیتونم حفظ کنم اینا رو و سریع یادم میره.
(۱۶ دى ۱۳۸۹ ۰۹:۲۵ ق.ظ)sepid نوشته شده توسط: متشکرم parsaNA.
ببخشید من الان کتاب لینزم همرام نیست.
توی کتاب لینز ننوشته چه جوری حالات ابتدایی DFA رو یکی می کنیم؟
خودم حدس میزنم از راه تبدیل به NFA معادلش و حالات ابتدایی رو یکی کنیم تو NFA بعد اون رو تبدیل به DFA کنیم چون تو تبدیلش حالت اولیه همون حالت اولیه NFA هست پس یک حالت میشه.
اما برای حالت نهایی نمیتونیم این کار رو انجام بدیم چون چند تا حالت نهایی مختلف ممکنه تولید بشه در تبدیل.
میشه ببینید روشش همینجوری هست یا نه؟
به خاطر این روش رو میپرسم چون من نمیتونم حفظ کنم اینا رو و سریع یادم میره.
خواهش می کنم .
بله یک روش همونی هست که شما فرمودین، یعنی:
بله یک روش همونی هست که شما فرمودین، یعنی:
- ابتدا یک راس جدید به نام q0 درست می کنیم و با انتقال لاندا به تمام راس های ابتدایی می ریم . اگه حتی یکی از راس های ابتدایی نهایی بود، راس q0 رو هم نهایی می کنیم . حالا یک NFA داریم که به DFA تبدیلش می کنیم.
روش دیگه ای هم هست که مشابهه . - یک وضعیت q0 به حالات ابتدایی اضافه می کنیم .اگه حتی یکی از راس های ابتدایی نهایی بود، راس q0 رو هم نهایی می کنیم . سپس همه انتقال هایی که راس های شروع دارند را به این راس جدید اضافه می کنیم. حالا ممکنه یه سری انتقال‌ها تکراری باشه که باعث میشه آتاماتا دیگه DFA نباشه . پس یک NFA داریم که به DFA تبدیلش می کنیم. تو این وضعیت دیگه حالت های ابتدایی قبلی رو حذف می کنیم .
فکر دچار یک اشتباه کوچک شدید
معادل هر nfa یک dfa وجود دارد یعنی dfa و nfa معادل هم هستند
پس میتوان گفت برای هر دو حالت می توان یک ماشین با یک حالت شروع و یک حالت نهایی وجود داشته باشد
ابتدا میتوان dfa با این شرایط را به یک nfa با چندین حالت شروع و پایان کشید و سپس این nfa را به dfa تبدیل کنیم
(۲۰ دى ۱۳۸۹ ۰۷:۰۳ ب.ظ)hatami84 نوشته شده توسط: فکر دچار یک اشتباه کوچک شدید
معادل هر nfa یک dfa وجود دارد یعنی dfa و nfa معادل هم هستند
پس میتوان گفت برای هر دو حالت می توان یک ماشین با یک حالت شروع و یک حالت نهایی وجود داشته باشد
ابتدا میتوان dfa با این شرایط را به یک nfa با چندین حالت شروع و پایان کشید و سپس این nfa را به dfa تبدیل کنیم
نه اشتباه نمیکنن در dfa برای اینکه یک وضعیت نهایی داشته باشیم باید وضعیتهای نهایی ادغام پذیر باشند که ممکنه نباشند ولی در nfa با لاندا میتونیم همه وضعیتها رو به یک وضعیت ببریم.
البته خود من به صورت صریح جواب سوال ۱ رو هیج جا ندیدم اما خوب ببینید طبق نظریه کاهش حالات DFA اگه ادغام پذیر باشند میتونند یکی باشند و این در مورد حالات ابتدایی و نهایی در DFA صدق میکند اگه دو تا حالت نهایی یا ابتدایی با هم یکسان (ادغام پذیر)نباشند هیج جوره نمیشه یکیشون کرد
در مورد NFA فکر میکنم دوستان جواب های جالبی دادند و تو جزوه دکتر منوچهری هم این مطلب با مثال و رسم شکل اومده