(۱۲ اردیبهشت ۱۳۹۱ ۰۳:۲۹ ق.ظ)Lakikharin نوشته شده توسط:  سلام. nfa شما زیاد حالت مسیر نداره و مشخصه چه رشته هایی رو قبول میکنه. یه حالت شروع داره. حتماً باید با a شروع بشه. بعدش میتونه یه تعداد b و بعدش c بیاد. عبارت منظمش میشه $aa^*b^*c^*$. یه تله هم باید داشته باشه چون اگه یه حرف اشتباه بگیره دیگه رشته جزء جواب نمیشه.

Lakikharin عزیز یه سوال بنابر nfa رشته acb پذیرفته میشه و به حالت نهایی میره که در عبارت منظمی که شما لطف کردید نوشتید قرار

نداره من میگم باید یکبار از راه مستقیم یا از راه حالت واسطه c به مقصد برسیم یعنی عبارت منظم میشه $(a^{ }b^{*}) (a^{ }c^{*}b^{*})$ ؟؟؟؟ خوشحال میشم نظرت رو بدونم

ببین دوست من تﺋوریک بخوای بدونی کتب لینز کامل توضیح داده اما عملی و رو مثال من برات شرح میدم :

اول باید از حالت اولیه $q0$ شروع کنیم چون دنبال dfa هستیم باید تمام حرکات q0 با $\sum ={a,b,c}$ را محاسبه کرد :

$(q0,a)=\left \{ q0,q1,q2 \right \}$ یعنی با شروع از q0 و یال a به سه حالت q0,q1,q2 می توان رسید .

حال $\left \{ q0,q1,q2 \right \}$ خود یک حالت است که باید مجزا حساب کنیم هر گره جدید ایجاد شد باید مجزا حساب کرد

حالا q0 رو با b حساب کنیم مب بینیم از q0 با b به هیچ حالت دیگه نمی تونیم بریم با c همینطور پس :
حالت ایجاد شده $\left \{ q0,q1,q2 \right \}$ را حساب کرده باید بدانیم چون q1 حالت نهایی است پس این حالت چون شامل q1 است پس حالت نهایی می باشد .باید دید تمام سه حالت مذکور یک بار با a و با b و با c چه حالاتی را شامل میشود :

گره جدید $\left \{q1,q2\right \}$ داریم این را هم مجزا حساب می کنیم :


حال گره ایجاد شده بعدی q1 را حساب می کنیم :

حال دقت کن اگه بخواییم q2 رو حساب کنیم چون از q0 هیچ راهی به q2 وجود ندارد موقع کاهش حالات می تونیم ازش صرف نظر کنیم حالا شکل رو من پیوست کردم
اگه اشکال دیدی بگو
سوال داشتی بپرس
بازم نفهمیدی دکمه کامل نیست رو بزن تا دوستان برات توضیح بدن

(۱۱ اردیبهشت ۱۳۹۱ ۰۶:۴۳ ب.ظ)yaser_ilam_com نوشته شده توسط:  ببین دوست من تﺋوریک بخوای بدونی کتب لینز کامل توضیح داده اما عملی و رو مثال من برات شرح میدم :

اول باید از حالت اولیه $q0$ شروع کنیم چون دنبال dfa هستیم باید تمام حرکات q0 با $\sum ={a,b,c}$ را محاسبه کرد :

$(q0,a)=\left \{ q0,q1,q2 \right \}$ یعنی با شروع از q0 و یال a به سه حالت q0,q1,q2 می توان رسید .

حال $\left \{ q0,q1,q2 \right \}$ خود یک حالت است که باید مجزا حساب کنیم هر گره جدید ایجاد شد باید مجزا حساب کرد

حالا q0 رو با b حساب کنیم مب بینیم از q0 با b به هیچ حالت دیگه نمی تونیم بریم با c همینطور پس :

$(q0,b)=(q0,c)=\varnothing$

حالت ایجاد شده $\left \{ q0,q1,q2 \right \}$ را حساب کرده باید بدانیم چون q1 حالت نهایی است پس این حالت چون شامل q1 است پس حالت نهایی می باشد .باید دید تمام سه حالت مذکور یک بار با a و با b و با c چه حالاتی را شامل میشود :

$(\left \{ q0,q1,q2 \right \},a)=\left \{ q0,q1,q2 \right \}$

$(\left \{ q0,q1,q2 \right \},b)=\left \{ q1 \right \}$

$(\left \{ q0,q1,q2 \right \},c)=\left \{ q1,q2 \right \}$

گره جدید $\left \{q1,q2\right \}$ داریم این را هم مجزا حساب می کنیم :

$(\left \{q1,q2\right \},a)=\varnothing$

$(\left \{q1,q2\right \},b)=\left \{q1 \right \}$

$(\left \{q1,q2\right \},c)=\left \{q1,q2 \right \}$

حال گره ایجاد شده بعدی q1 را حساب می کنیم :

$(\left \{q1\right \},a)=\varnothing$

$(\left \{q1\right \},b)=\left \{q1 \right \}$

$(\left \{q1\right \},c)=\varnothing$

حال دقت کن اگه بخواییم q2 رو حساب کنیم چون از q0 هیچ راهی به q2 وجود ندارد موقع کاهش حالات می تونیم ازش صرف نظر کنیم حالا شکل رو من پیوست کردم
اگه اشکال دیدی بگو
سوال داشتی بپرس
بازم نفهمیدی دکمه کامل نیست رو بزن تا دوستان برات توضیح بدن

با تشکر از جوابتان با توجه یه توضیحاتی که دادید در درک مورد زیر دچار اشکال شدم
$(\left \{ q0,q1,q2 \right \},c)=\left \{ q1,q2 \right \}$
مگر نه این است که از حالت q2 با مقدار c به همان حالت باز می گردیم و از حالت های q0,q1 با مقدار c نمی توان به جایی رفت ایا جواب مورد بالا q2 نمی باشد؟
در ضمن ایا حالت تهی نیز تله نیست چون نه نهایی است نه از ان می توان به جایی رفت

دوست من بازم تاکید می کنم با اینکه اقای Lakikharin هم تایید کردن سوال رو پس سوال درسته می مونه شرحش اگه نفهمیدی دقیقا بگو کجای سوال رو تا بازم برات توضیح بدم

موفق باشی

متشکر. مثل اینکه جای b و c رو عوض کردم. عبارت منظمش میشه $aa^*c^*b^*$ که میشه بفرم $a^ c^*b^*$ هم نوشت. الآن درستش میکنم.