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

رسم 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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  شمارش تعداد state های ماشین DFA mostafa2012 ۱۰ ۵,۲۹۶ ۱۳ بهمن ۱۳۹۳ ۱۲:۱۷ ب.ظ
آخرین ارسال: fatemeh69
  بدست آوردن عبارت منظم یک dfa mostafa2012 ۸ ۲,۰۳۲ ۰۳ بهمن ۱۳۹۳ ۰۲:۲۴ ق.ظ
آخرین ارسال: Jooybari
Question زبان منظم، DFA، حافظه، به خاطر آوردن! Ametrine ۷ ۲,۰۲۴ ۲۹ دى ۱۳۹۳ ۱۱:۴۰ ب.ظ
آخرین ارسال: Ametrine
  تبدیل nfa به dfa alirezafchh ۱ ۱,۴۲۰ ۰۸ دى ۱۳۹۳ ۱۲:۴۷ ق.ظ
آخرین ارسال: fatemeh69
  مشکل با مثال ۲-۶ از کتاب پیتر لینز (فصل ۲ ویرایش ۵) ؟ post98 ۱ ۸۱۱ ۱۶ آبان ۱۳۹۳ ۰۳:۱۵ ب.ظ
آخرین ارسال: Aliteh
Question توضیح شیوه تبدیل NFA به DFA براساس این شکل s_t_6 ۲ ۴,۱۱۸ ۲۴ مرداد ۱۳۹۳ ۱۲:۳۵ ب.ظ
آخرین ارسال: fatemeh69
  گراف dfa این زبان چه شکلیست s_t_6 ۵ ۱,۲۰۸ ۰۳ مرداد ۱۳۹۳ ۱۲:۳۳ ق.ظ
آخرین ارسال: Aliteh
Smile گراف رسم شده برای این زبان منظم چه ایرادی دارد و چرا s_t_6 ۸ ۱,۵۶۰ ۳۱ تیر ۱۳۹۳ ۰۶:۱۶ ب.ظ
آخرین ارسال: Jooybari
  فرق FSA و DFA joyebright ۳ ۷۶۸ ۰۲ اردیبهشت ۱۳۹۳ ۰۹:۲۳ ب.ظ
آخرین ارسال: hosshah
  جدول حالت یک DFA Talnetir ۴ ۸۴۵ ۲۴ اسفند ۱۳۹۲ ۰۷:۴۵ ب.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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