پاسخ شما دوست عزیز:

1. برای هر NFA با چندین وضعیت نهایی‌، یک NFA معادل با فقط یک وضعیت نهایی وجود دارد . اما این حکم برای DFA صادق نیست( طبق کتاب لینز )
   

   ---

2. برای هر DFA با چندین وضعیت ابتدایی‌، یک DFA معادل با فقط یک وضعیت ابتدایی وجود دارد . این حکم برای NFA هم صادق است( طبق کتاب لینز )
   

متشکرم parsaNA.
ببخشید من الان کتاب لینزم همرام نیست.
توی کتاب لینز ننوشته چه جوری حالات ابتدایی DFA رو یکی می کنیم؟
خودم حدس میزنم از راه تبدیل به NFA معادلش و حالات ابتدایی رو یکی کنیم تو NFA بعد اون رو تبدیل به DFA کنیم چون تو تبدیلش حالت اولیه همون حالت اولیه NFA هست پس یک حالت میشه.
اما برای حالت نهایی نمیتونیم این کار رو انجام بدیم چون چند تا حالت نهایی مختلف ممکنه تولید بشه در تبدیل.
میشه ببینید روشش همینجوری هست یا نه؟
به خاطر این روش رو میپرسم چون من نمیتونم حفظ کنم اینا رو و سریع یادم میره.

(۱۶ دى ۱۳۸۹ ۰۹:۲۵ ق.ظ)sepid نوشته شده توسط:  متشکرم parsaNA.
ببخشید من الان کتاب لینزم همرام نیست.
توی کتاب لینز ننوشته چه جوری حالات ابتدایی DFA رو یکی می کنیم؟
خودم حدس میزنم از راه تبدیل به NFA معادلش و حالات ابتدایی رو یکی کنیم تو NFA بعد اون رو تبدیل به DFA کنیم چون تو تبدیلش حالت اولیه همون حالت اولیه NFA هست پس یک حالت میشه.
اما برای حالت نهایی نمیتونیم این کار رو انجام بدیم چون چند تا حالت نهایی مختلف ممکنه تولید بشه در تبدیل.
میشه ببینید روشش همینجوری هست یا نه؟
به خاطر این روش رو میپرسم چون من نمیتونم حفظ کنم اینا رو و سریع یادم میره.

فکر دچار یک اشتباه کوچک شدید
معادل هر nfa یک dfa وجود دارد یعنی dfa و nfa معادل هم هستند
پس می‌توان گفت برای هر دو حالت می توان یک ماشین با یک حالت شروع و یک حالت نهایی وجود داشته باشد
ابتدا میتوان dfa با این شرایط را به یک nfa با چندین حالت شروع و پایان کشید و سپس این nfa را به dfa تبدیل کنیم

(۲۰ دى ۱۳۸۹ ۰۷:۰۳ ب.ظ)hatami84 نوشته شده توسط:  فکر دچار یک اشتباه کوچک شدید
معادل هر nfa یک dfa وجود دارد یعنی dfa و nfa معادل هم هستند
پس می‌توان گفت برای هر دو حالت می توان یک ماشین با یک حالت شروع و یک حالت نهایی وجود داشته باشد
ابتدا میتوان dfa با این شرایط را به یک nfa با چندین حالت شروع و پایان کشید و سپس این nfa را به dfa تبدیل کنیم

نه اشتباه نمیکنن در dfa برای اینکه یک وضعیت نهایی داشته باشیم باید وضعیتهای نهایی ادغام پذیر باشند که ممکنه نباشند ولی در nfa با لاندا میتونیم همه وضعیتها رو به یک وضعیت ببریم.

البته خود من به صورت صریح جواب سوال ۱ رو هیج جا ندیدم اما خوب ببینید طبق نظریه کاهش حالات DFA اگه ادغام پذیر باشند میتونند یکی باشند و این در مورد حالات ابتدایی و نهایی در DFA صدق میکند اگه دو تا حالت نهایی یا ابتدایی با هم یکسان (ادغام پذیر)نباشند هیج جوره نمیشه یکیشون کرد

در مورد NFA فکر میکنم دوستان جواب های جالبی دادند و تو جزوه دکتر منوچهری هم این مطلب با مثال و رسم شکل اومده