رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز - نسخه‌ی قابل چاپ

رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز - g_monireh - 29 اردیبهشت ۱۳۹۲ ۱۲:۱۹ ق.ظ کتاب لینز مثال۴-۴ اگر ممکنه یه توضیح برای رسم dfa مربوط به L1/L2 در مثال ۴-۴ از کتاب لینز بدید. مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید. مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز - Jooybari - 29 اردیبهشت ۱۳۹۲ ۱۲:۳۹ ق.ظ سلام. کاری با dfa شکل نداشته باشید. توی شکل میتونست از q0 با b به q5 بره و حالات ۳ و ۴ رو حذف کنه. زبانی که از تقسیم ایجاد میشه رشته های زبان اوله که از آخرشون حداقل یک b کم شده. رشته های حاصل همون [tex]a^ b^*[/tex] هستن.

RE: رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز - azad_ahmadi - 29 اردیبهشت ۱۳۹۲ ۰۱:۰۴ ق.ظ با توجه به زبانهای زیر : همونطور که در کتاب لینز هم نوشته شده برای اینکه بتونیم L1/L2 رو بتونیم بدست بیاریم ابتدا ماشنی DFA زبان L1 رو میکشیم (همون کاری که در تصویر شما هم انجام دادید). بعد از این کار یک کپی از همین شکل بالایی رو هم می کشیم اما بدون حالت پایانی (توجه کن که تو کتاب لینز هم گفته یک کپی از ماشین زبان L1 را کشیده و حالات پایانی را رسم نمی کنیم). حالا برای "هر حالت از ماشین زبان L1" باید زبان L2 رو بررسی کرد تا بدونیم که آیا رشته ای هست که توست این ماشین L1 پذیرش بشه (توجه کن که برای هر حالت این کار رو انجام میدیم و پذیرش زمانی کامل میشه که به یه حالت پایانی برسیم). اگه از یک حالتی که شروع کردیم با طی مراحلی رشته پذیرش شد، اون حالت رو در کپی گرفته شده به حالت پایانی تبدیل می کنیم. اگه تو جواب هم دقت کنید می بینید که همین کار رو کرده، اما زبان L1 که ab رو هم پذیرش میکرد، تو جواب دیگه پذیرش ab ممکن نیست. چرا که تو مسیری که باعث پذیرش ab در زبان L1 میشه نمی تونیم زبان L2 رو پذیرش کنیم و به حالت پایانی هم بریم.

رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز - g_monireh - 29 اردیبهشت ۱۳۹۲ ۰۹:۳۰ ق.ظ تشکر از توضیحات کاملتون. رسم dfa رو کاملا متوجه شدم. فقط توضیحاتی که Jooybari دادن رو یکم مشکل دارم. چرا باحذف حداقل یک b یا بیشتر باز به همون رشته L1 میرسیم.؟؟؟ شرمنده من تازه نظریه زبان رو شروع کردم بخاطر همین ممکنه سوالاتم پیش پا افتاده باشه.

RE: رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز - azad_ahmadi - 29 اردیبهشت ۱۳۹۲ ۰۱:۲۲ ب.ظ این حق شماست که در مانشت هرچقدر سوال دارید بپرسید تا دوستان دیگه درحد امکان مشکل شمارو برطرف کنند. ببینید تعریفی ساده ای برای [tex]L1/L2[/tex] به این صورت هست: ////// تمام پیشوند های زبان [tex]L1[/tex] که پسوند آنها (پسوند همان پیشوندهای زبان [tex]L1[/tex]) در زبان [tex]L2[/tex] موجود باشد. بصورت ریاضی هم به این صورت هست : [tex]L1/L2 : \, \, \left \{ x\, \epsilon \sum ^{*} \, | \, xy\, \epsilon \, L1 , y\, \, \epsilon L2 \right \}[/tex] /////// پس نتیجه نهایی برای ما همون پیشوندهای زبان L1 هست که پسوند اونا در زبان L2 وجود داره. همونطور که آقای جویباری هم گفتند، اگه در زبان L2 حداقل یک b رو حذف کنیم، زبان موجود میشه نتیجه L1/L2 چرا که در زبان L1 رشته میتونه با b تموم نشه، اما در زبان L2 رشته حداقل یک b باید داشته باشه (چون m>=1 هست). پس با حداقل حدف یک b در زبان L2 جواب بدست میاد. موفق باشید.

رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز - g_monireh - 29 اردیبهشت ۱۳۹۲ ۰۲:۰۲ ب.ظ خیلی ممنونم