زمان کنونی: ۰۷ دى ۱۴۰۳, ۰۳:۳۰ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

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

ارسال:
  

g_monireh پرسیده:

Question رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز

کتاب لینز مثال۴-۴
اگر ممکنه یه توضیح برای رسم dfa مربوط به L1/L2 در مثال ۴-۴ از کتاب لینز بدید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.



مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

۱
ارسال:
  

azad_ahmadi پاسخ داده:

RE: رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز

با توجه به زبانهای زیر :

[تصویر:  182483_1_1379083453.jpg]


همونطور که در کتاب لینز هم نوشته شده برای اینکه بتونیم L1/L2 رو بتونیم بدست بیاریم
ابتدا ماشنی DFA زبان L1 رو میکشیم (همون کاری که در تصویر شما هم انجام دادید).

[تصویر:  182483_2_1379083453.jpg]

بعد از این کار یک کپی از همین شکل بالایی رو هم می کشیم اما بدون حالت پایانی (توجه کن که تو کتاب لینز هم گفته یک کپی از ماشین زبان L1 را کشیده و حالات پایانی را رسم نمی کنیم).
حالا برای "هر حالت از ماشین زبان L1" باید زبان L2 رو بررسی کرد تا بدونیم که آیا رشته ای هست که توست این ماشین L1 پذیرش بشه (توجه کن که برای هر حالت این کار رو انجام میدیم و پذیرش زمانی کامل میشه که به یه حالت پایانی برسیم).
اگه از یک حالتی که شروع کردیم با طی مراحلی رشته پذیرش شد، اون حالت رو در کپی گرفته شده به حالت پایانی تبدیل می کنیم.
اگه تو جواب هم دقت کنید می بینید که همین کار رو کرده، اما زبان L1 که ab رو هم پذیرش میکرد، تو جواب دیگه پذیرش ab ممکن نیست.
چرا که تو مسیری که باعث پذیرش ab در زبان L1 میشه نمی تونیم زبان L2 رو پذیرش کنیم و به حالت پایانی هم بریم.

[تصویر:  182483_3_1379083453.jpg]

۱
ارسال:
  

Jooybari پاسخ داده:

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

سلام. کاری با dfa شکل نداشته باشید. توی شکل میتونست از q0 با b به q5 بره و حالات ۳ و ۴ رو حذف کنه. زبانی که از تقسیم ایجاد میشه رشته های زبان اوله که از آخرشون حداقل یک b کم شده. رشته های حاصل همون [tex]a^ b^*[/tex] هستن.

۰
ارسال:
  

g_monireh پاسخ داده:

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

تشکر از توضیحات کاملتون. رسم dfa رو کاملا متوجه شدم. فقط توضیحاتی که Jooybari دادن رو یکم مشکل دارم. چرا باحذف حداقل یک b یا بیشتر باز به همون رشته L1 میرسیم.؟؟؟
شرمنده من تازه نظریه زبان رو شروع کردم بخاطر همین ممکنه سوالاتم پیش پا افتاده باشه.

ارسال:
  

azad_ahmadi پاسخ داده:

RE: رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز

این حق شماست که در مانشت هرچقدر سوال دارید بپرسید تا دوستان دیگه درحد امکان مشکل شمارو برطرف کنند. Smile

ببینید تعریفی ساده ای برای [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 جواب بدست میاد.

موفق باشید.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

g_monireh پاسخ داده:

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

خیلی ممنونم Smile



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تست ۸۷ کامپیوتر مربوط به عامل ها Shekarchi_shab ۳ ۲,۵۹۶ ۲۰ بهمن ۱۴۰۱ ۰۷:۳۹ ب.ظ
آخرین ارسال: HamidReza1
  رسم مدار انکدر ۴ به ۲ moslemrahmati ۰ ۱,۹۴۳ ۲۶ اسفند ۱۳۹۸ ۰۲:۰۷ ب.ظ
آخرین ارسال: moslemrahmati
  آخرین اخبار مربوط به مسابقات رباتیک کشوری javadjj ۲۴ ۲۳,۱۸۱ ۲۳ دى ۱۳۹۸ ۱۲:۵۶ ق.ظ
آخرین ارسال: marvelous
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۲,۹۸۱ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous
  رسم مستطیل با ماوس در اسمبلی Zmf ۰ ۱,۵۳۰ ۰۴ خرداد ۱۳۹۸ ۰۶:۱۶ ب.ظ
آخرین ارسال: Zmf
  اهمیت طراحی جلد کتاب یا مجله hora27 ۰ ۲,۰۱۸ ۲۹ اردیبهشت ۱۳۹۸ ۰۵:۱۰ ب.ظ
آخرین ارسال: hora27
Question رسم درخت با ۲۶ گره و ارتفاع کمینه porseshgar ۰ ۱,۷۶۲ ۱۶ بهمن ۱۳۹۷ ۱۲:۱۱ ب.ظ
آخرین ارسال: porseshgar
  بهترین کتاب برای یادگیری ریاضی ۱ چیه ؟ radar ۰ ۲,۰۰۱ ۱۹ دى ۱۳۹۷ ۱۲:۲۹ ب.ظ
آخرین ارسال: radar
Star بهترین و پر درآمدترین شغل مربوط به کامپیوتر از نظر شما چیست؟ پشتکار ۶ ۱۳۲ ۱۴ آذر ۱۳۹۷ ۰۵:۱۴ ب.ظ
آخرین ارسال: jaweed88
  آیا امکان ارسال مجدد ایمیل مربوط به پذیرش مقاله در یک ژورنال isi وجود دارد؟ Autumngirl ۴ ۴,۲۹۶ ۱۱ مهر ۱۳۹۷ ۰۱:۲۱ ب.ظ
آخرین ارسال: Autumngirl

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close