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

سلام دوستان
تو خیلی جزوه ها و PDFها دنبال این موضوع گشتم اما هیچکدوم به این موضوع نپرداخته، کتاب سود کمپ هم اینقدر بد نوشته که نمی فهمم چی می گه، لطفا اگر امکان داره دوستان روشش رو شرح بدن
ممنون و سپاسگزارم

منظورتون تبدیل nfa به dfa ست؟
آخه من همچین چیزی توی کتاب لینز ترجمه صراف زاده ندیدم!!!!
منظورتون حذف لامدا از nfaست ?
اگه منظورتون اینه تا توضیح بدم.

تو جزوه یکی از اساتید این تیتر رو دیدم، اما جزوه اش غلط املایی چاپی زیاد داشت نفهمیدم چه جوری تبدیل کرده، تو اون جزوه علاوه بر همه تبدیل های دیگه این تبدیل یعنی تبدیل nfaنوع لامبدا به nfa(یا فکر می کنم همون حذف لامبدا) بیان شده بود.
حالا اگه اطلاعاتی دارین ممنون می شم راهنمایی کنید

ببینید ما در nfa راه های زیادی برای تبدیل به شکل های دیگه داریم.
خوب حالا میخوایم لامدا رو حذف کنیم ، پس اینو باید شبیه سازی کنیم.
از وضعیت اول شروع میکنیم. اگر با لامدا به هر وضعیت دیگه ای متصل بود ما تمام خروجی های ممکن رو برای همه این وضعیت ها چک میکنیم.و نام همه وضعیت هایی که با این خروجی خاص به وضعیت حاضر متصلند رو داخل یه وضعیت جدید مینویسیم و یک یال بابرچسب اون خروجی بهش رسم میکنیم(البته تمام این وضعیت ها که نوشتیم هم ممکنه که با لامدا به وضعیت های دیگه ای وصل باشند که نام اونها رو هم مینویسیم).
حالا از این وضعیت های جدید تمام خروجی ها رو چک میکنیم. هر خروجی رو برای تمام وضعیت هایی که اسمشون رو داخل این وضعیت نوشتیم چک میکنیم، اگر ارتباطی با این خروجی از هرکدام به هر وضعیتی بود نام آن وضعیت رو در وضعیت جدید مینویسیم(البته اینبار هم باید وضعیت های متصل با لامدا رو مثل دفعه قبل در نظر داشته باشید).
اگر وضعیت جدید تماما مشابه وضعیتی باشد که قبلا ساختیم(یعنی تمام نام هایی که داخلشونه مشابه باشن) این وضعیت رو حذف و یال رو به وضعیتی که قبلا ساختیم وصل میکنیم.
این کارارو تا وقتی که دیگه هیچ وضعیتی قابل تولید جدید نباشه ادامه میدیم.
.حالا هر وضعیتی که نام یکی از وضعیت های نهایی در شکل اولیه رو شامل میشه به وضعیت پایانی تبدیل میکنیم.

من یک مثال غیر مهندسی ضمیمه کردم که شاید خیلی مناسب نباشه اما به یاد گیری هرچند کم اما کمک میکنه.
اول ضمیمه رو دانلود کنید و بعد با توجه به اون و توضیحات بالا به توضیحات زیر توجه کنید.

nfa بالایی که توضیح داده شد که چه زبانی رو میپذیره.
خوب دیگه در مورد ماشین بالایی توضیح ندم بهتره .
ماشین پایینی 6 وضعیت داره که به جای نامشون یه عدد بالاشون نوشته شده که با اون ارجاع میدیم.
و ضعیت 1 چون در nfa بالایی q0 با لامدا به q1 یالی داشت ما نام هر دو وضعیت را در این وضعیت جدید نوشتیم.
خوب حالا ما از q1 میتونیم با a و b خارج شیم و از q0 فقط میتونیم با b خارج شیم , پس از وضعیت جدید فقط میتونیم با a و b خارج شیم. اول a رو میکشیم که فقط ازq1 میتونیم به q9 بریم پس یک وضعیت جدید(که در شکل با 2 علامت گذاری شده) میسازیم و q9 را داخلش مینوسیم. خوب حالا نوبت b ست . از q0 با b میتونیم بریم به q2 اما چون q2 با لامدا به q5 راه داره نام هر دو ی این وضعیت هارو داخل وضعیت جدید مینویسیم. و چون از q1 نیز با b میتونیم به q8 بریم نام q8 رو هم به همین وضعیت اضافه میکیم(وضعیت اندیس 3).
خوب از q9 که خروجی نداریم پس به وضعیت اندیس 3 می پردازیم. در این وضعیت q2 و q5 و q8 قرار دارند. میبینیم که از q2 به خودش راه داره و چون q2 با لامدا به q5 راه هست ,وضعیت 7 رو میسازیم و در وضعیت 7 از q2 با b دوباره q2 راه هست و q2 هم با لامدا به q5 راه داره دوباره وضعیتی شبیه به 7 ایجاد میشه که به جای دوباره نویسی یک حلقه به خود 7 میزنیم. و با c از q2 و q5 به q3 و q6 راه هست .که وضعیت جدیدی(وضعیت 4) میسازیم و از وضعیت 7 با c به وضعیت 4 یالی رسم میکنیم.
خوب دوباره بریم سر وضعیت 3 با خروجی b . خب میبینیم که از بین وضعیت های داخل وضعیت 3 فقط ، وضعیت q8 با b خروجی دارد و آنهم دوباره به q8 پس یک وضعیت جدید میسازیم (وضعیت 8) و q8 را به آن اضافه میکنیم. حالا در وضعیت 8 چون فقط q8 وجود دارد و q8 هم با b به خودش . پس از وضعیت 8 با b حلقه میزنیم.
خوب دوباره وضعیت 3 با خروجی c که از q2 به q3 و از q5 به q6 یالی وجود دارد که q3 و q6 همان وضعیت 4 را تشکیل میدهن که فقط نیاز است که یالی از وضعیت 3 به وضعیت 4 با برچسب c رسم میکنیم.
خوب دیگه فکر کنم بقیش توضیح نخواد که از وضعیت 4 چرا به وضعیت 5 و 6 یال کشیدیم.
فقط اینو توضیح بدم که وضعیت 2 به دلیل وجود q9 و وضعیت 3 به دلیل وجود q8 و وضعیت 8 به دلیل وجود q8 و وضعیت 6 به دلیل وجود q7 و وضعیت 5 نیز به دلیل وجود q4 به وضعیت پایانی تبدیل شده اند.

اگر مشکلی هست یا جایی گنگه بگید که توضیح بدم

ممنون واقعا لطف کردید، لطفا هر موقع که فرصت داشتید مثال رو هم ضمیمه کنید واقعا سپاسگزارم

(30 خرداد 1391 07:58 ب.ظ)fa_karoon نوشته شده توسط: [ -> ]سلام دوستان
تو خیلی جزوه ها و PDFها دنبال این موضوع گشتم اما هیچکدوم به این موضوع نپرداخته، کتاب سود کمپ هم اینقدر بد نوشته که نمی فهمم چی می گه، لطفا اگر امکان داره دوستان روشش رو شرح بدن
ممنون و سپاسگزارم

سلام.
یه جدول درست می کنیم برای همه حالت ها مثلا :

a b
-------------------------------------------------------------
1 q0
2 q1
3 q2
-------------------------------------------------------------

منظور اینکه q0 با a به کدوم حالت ها میره و با b به کدوم حالت ها.
بعد اینکه اینارو مشخص کردی، حالات جدید هم که زیر ستون b و a ایجاد شده رو هم همین کار رو باهاش انجام میدیم.
مثلا برای q0 زیر a نوشته شده q1.q2 . حالا خود q1,q2 رو هم به ستون اول (شماره 4) اضافه می کنیم. و برای اون هم a,b رو مشخص میکنیم. حالا اگه برسیم به جایی که حالت جدید پیش نیاد، هر تعداد (1 و 2 و 3 و ...) که تو ستون اول داریم تعداد حالاتمونه. و زیر ستون a,b هم مشخص شده هر کدوم از اونها با a کجا می رن و با b کجا می رن. آخر سر هم که باید حالات پایانی رو مشخص کنیم، توی nfa هر حالتی که پایانی باشه باید توی dfa معادل هم حالات پایانی درنظر گرفته بشه.
اگه مشکل داشتی بگو حل کنیم.
موفق باشی.

تو همون پست واستون ضمیمه کردم امیدوارم که مفید باشه.
یه مقدار توضیح رونش سخت بود . و حجمش زیاد میشد و من فرصتم کم بود. موضوع سختی نیست . امیدوارم که تونسته باشم کمک کنم.

اولا از همه ی دوستانی که واقعا زحمت می کشن نهایت سپاسگزاری رو دارم.
فقط خواستم منم به نوبه ی خودم خلاصه مطلب رو بنویسم:
برای تبدیل NFA( یا nonDFA ) لاندا ، به NDF بدون لاندا، کافیه کاری کنیم لانداها حذف بشن بون اینکه عملکرد ماشین تغییر کنه.اگه نکته ای رو جا گذاشتم دوستان تذکر بدن .
==
یه سری شکل و slide هم در این زمینه داشتم که اگه یادم باشه بعدا ضمیمه می کنم.