۰
subtitle
ارسال: #۱
  
رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز
۱
ارسال: #۲
  
RE: رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز
با توجه به زبانهای زیر :
همونطور که در کتاب لینز هم نوشته شده برای اینکه بتونیم L1/L2 رو بتونیم بدست بیاریم
ابتدا ماشنی DFA زبان L1 رو میکشیم (همون کاری که در تصویر شما هم انجام دادید).
بعد از این کار یک کپی از همین شکل بالایی رو هم می کشیم اما بدون حالت پایانی (توجه کن که تو کتاب لینز هم گفته یک کپی از ماشین زبان L1 را کشیده و حالات پایانی را رسم نمی کنیم).
حالا برای "هر حالت از ماشین زبان L1" باید زبان L2 رو بررسی کرد تا بدونیم که آیا رشته ای هست که توست این ماشین L1 پذیرش بشه (توجه کن که برای هر حالت این کار رو انجام میدیم و پذیرش زمانی کامل میشه که به یه حالت پایانی برسیم).
اگه از یک حالتی که شروع کردیم با طی مراحلی رشته پذیرش شد، اون حالت رو در کپی گرفته شده به حالت پایانی تبدیل می کنیم.
اگه تو جواب هم دقت کنید می بینید که همین کار رو کرده، اما زبان L1 که ab رو هم پذیرش میکرد، تو جواب دیگه پذیرش ab ممکن نیست.
چرا که تو مسیری که باعث پذیرش ab در زبان L1 میشه نمی تونیم زبان L2 رو پذیرش کنیم و به حالت پایانی هم بریم.
همونطور که در کتاب لینز هم نوشته شده برای اینکه بتونیم L1/L2 رو بتونیم بدست بیاریم
ابتدا ماشنی DFA زبان L1 رو میکشیم (همون کاری که در تصویر شما هم انجام دادید).
بعد از این کار یک کپی از همین شکل بالایی رو هم می کشیم اما بدون حالت پایانی (توجه کن که تو کتاب لینز هم گفته یک کپی از ماشین زبان L1 را کشیده و حالات پایانی را رسم نمی کنیم).
حالا برای "هر حالت از ماشین زبان L1" باید زبان L2 رو بررسی کرد تا بدونیم که آیا رشته ای هست که توست این ماشین L1 پذیرش بشه (توجه کن که برای هر حالت این کار رو انجام میدیم و پذیرش زمانی کامل میشه که به یه حالت پایانی برسیم).
اگه از یک حالتی که شروع کردیم با طی مراحلی رشته پذیرش شد، اون حالت رو در کپی گرفته شده به حالت پایانی تبدیل می کنیم.
اگه تو جواب هم دقت کنید می بینید که همین کار رو کرده، اما زبان L1 که ab رو هم پذیرش میکرد، تو جواب دیگه پذیرش ab ممکن نیست.
چرا که تو مسیری که باعث پذیرش ab در زبان L1 میشه نمی تونیم زبان L2 رو پذیرش کنیم و به حالت پایانی هم بریم.
۱
ارسال: #۳
  
رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز
سلام. کاری با dfa شکل نداشته باشید. توی شکل میتونست از q0 با b به q5 بره و حالات ۳ و ۴ رو حذف کنه. زبانی که از تقسیم ایجاد میشه رشته های زبان اوله که از آخرشون حداقل یک b کم شده. رشته های حاصل همون [tex]a^ b^*[/tex] هستن.
۰
ارسال: #۴
  
رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز
تشکر از توضیحات کاملتون. رسم dfa رو کاملا متوجه شدم. فقط توضیحاتی که Jooybari دادن رو یکم مشکل دارم. چرا باحذف حداقل یک b یا بیشتر باز به همون رشته L1 میرسیم.؟؟؟
شرمنده من تازه نظریه زبان رو شروع کردم بخاطر همین ممکنه سوالاتم پیش پا افتاده باشه.
شرمنده من تازه نظریه زبان رو شروع کردم بخاطر همین ممکنه سوالاتم پیش پا افتاده باشه.
ارسال: #۵
  
RE: رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز
این حق شماست که در مانشت هرچقدر سوال دارید بپرسید تا دوستان دیگه درحد امکان مشکل شمارو برطرف کنند.
ببینید تعریفی ساده ای برای [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 جواب بدست میاد.
موفق باشید.
ببینید تعریفی ساده ای برای [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 جواب بدست میاد.
موفق باشید.
۰
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close