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

لطفا عبارت منظم این زبانها رو بنوسید:

l={vwv : v,w {a,b}* , |v|<=3 و
l={w: (n(a)-n(b)) mod 3 <>0}

سلام.
زبان اولی چون محدودیتی روی v قرار داده پس زبان منظم هست و عبارت منظمی رو میشه براش نوشت. البته عبارت منظمش رو باید بصورت دستی و با دقت نوشت بطوری که طول V بزرگتر مساوی 3 باشد.حالات مختلفی بوجود میاد که باید همه اینارو درج کرد. حالات به اینصورت هستن:
[tex]aaaWaaa[/tex]
[tex]bbbWbbb[/tex]
[tex]abaWaba[/tex]
[tex]baaWbaa[/tex]
[tex]aabWaab[/tex]
[tex]babWbab[/tex]
[tex]bbaWbba[/tex]
[tex]abbWabb[/tex]

که [tex]W = (a b)^{*}[/tex] است.

البته این عبارت منظم ناقص هست و باید در هرصورت لامبدا رو قبول کنه، صرفا جهت دهی به پاسخ بود.

سلام. لطفاً از این به بعد هر سوال رو با عنوان مناسب تر مطرح کنید و در هر موضوع هم فقط یک سوال قرار بدید. عنوان موضوع رو ویرایش کردم.

پاسخ سوال اول:
چون v<=3 هست و با درنظر گرفتن v=0 به سیکما استار میرسیم نباز به نوشتن بقیه حالات نیست. پس زبان میشه [tex](a b)^*[/tex]
یعنی اگه L زبان سوال باشه میشه نوشت L=L0∪L1∪L2∪L3 که Liها رو حالتی از زبان که طول v برابر i باشن فرض کنید. تا اینحا قبول!؟!؟
اول L0 رو محاسبه میکنیم یعنی حالتی که طول v برابر صفره که زبانمون میشه سیکمااستار. میدونیم که اجتماع سیکمااستار با هر زبانی بازهم سیکمااستار میشه. پس نیازی نیست بقیه رو حساب کنیم. L هم سیکمااستار میشه.

پاسخ سوال دوم:
برای این زبا میتونید به راحتی یه dfa با سه حالت طراحی کنید و بعد dfa رو به عبارت منظم تبدیل کنید.
عبارتش میشه ((ab+(b+aa)(ba)*(a+bb))*(a+(b+aa)(ba)*(λ+b) و ماشینش هم در فایل ضمیمه آوردم:

موفق باشید.

(13 دى 1392 06:11 ب.ظ)Jooybari نوشته شده توسط: [ -> ]پاسخ سوال اول:
چون v<=3 هست و با درنظر گرفتن v=0 به سیکما استار میرسیم نباز به نوشتن بقیه حالات نیست. پس زبان میشه [tex](a b)^*[/tex]

سلام
من هنوز توی این سوال گیرم ، سرچ زدم و دیدم قبلا یکی تاپیکش رو زده دیگه من خداروشکر تاپیک تکراری نزدم

توی صورت سوال گفته شده V<=3 ، پس طول رشته V می تونه صفر باشه (لامبدا) یا یک باشه یا دو باشه یا حداکثر سه باشه ، که اگه صفر باشه که هیچی ، اما اگه یک باشه دو حالت پیدا میکنه ، V می تونه a باشه یعنی aWa یا b باشه یعنی bWb و اگر طول V دو باشه ، چهار حالت پیدا میکنه میتونه aaWaa و abWab و baWba و bbWbb باشه و اگر طولش سه باشه میشه 8 حالت مختلف ، حالا من متوجه نمی شم چرا طول v رو صفر در نظر می گیریم؟
*(a+b) یعنی تمام رشته های متشکل از a و b ، یعنی مثلا فرض بگیریم رشته abbbbabb هم میشه ساخت حالا اگه طول رشته v رو یک در نظر بگیریم vی اول رشته میشه a و vی آخر رشته میشه b یا اگه طول V رو دو در نظر بگیریم vی اول رشته میشه ab و vی آخر رشته میشه bb
متوجه نمیشم چرا میشه *(a+b) ؟ یکی میشه کامل توضیح بده؟
مگه v اول رشته با v آخر رشته نباید یکی باشه؟

(20 تير 1393 12:07 ق.ظ)Aliteh نوشته شده توسط: [ -> ]توی صورت سوال گفته شده V<=3 ، پس طول رشته V می تونه صفر باشه (لامبدا) یا یک باشه یا دو باشه یا حداکثر سه باشه ، که اگه صفر باشه که هیچی ، اما اگه یک باشه دو حالت پیدا میکنه ، V می تونه a باشه یعنی aWa یا b باشه یعنی bWb و اگر طول V دو باشه ، چهار حالت پیدا میکنه میتونه aaWaa و abWab و baWba و bbWbb باشه و اگر طولش سه باشه میشه ۸ حالت مختلف ، حالا من متوجه نمی شم چرا طول v رو صفر در نظر می گیریم؟

سلام. شاید بد توضیح داده باشم. ما طول v رو صفر درنظر نمیگیریم. اگه L زبان سوال باشه میشه نوشت [tex]L=L0\cup L1\cup L2\cup L3[/tex] که [tex]Li[/tex]ها رو حالتی از زبان که طول v برابر i باشن فرض کنید. تا اینحا قبول!؟!؟
اول L0 رو محاسبه میکنیم یعنی حالتی که طول v برابر صفره که زبانمون میشه سیکمااستار. میدونیم که اجتماع سیکمااستار با هر زبانی بازهم سیکمااستار میشه. پس نیازی نیست بقیه رو حساب کنیم. L هم سیکمااستار میشه.