سوال ۱ شرمنده یکم طولانی میشه جوابش، منم فرصت ندارم.
فقط سوال دوم رو جواب میدم که خیر هیچ زبانی وجود نداره که توی این رابطه صدق کنه.
چون سمت راستی حتما لاندا داره(به دلیل ستاره روی کل عبارت) ولی در سمت چپی به هیچ عنوان امکان نداره که لاندا داشته باشه(به دلیل مکمل گرفتن از یه بستارستاره ای(بستار ستاره ای حتما شامل لانداست و وقتی مکمل بگیریم، حتما فاقد لاندا میشه) )

سلام. سوال اول:

طول رشته رو ثابت درنظر میگیریم:
فرض اولیه: فرض میکنیم اندازه رشته برابر k و توان هم برابر ۰ باشه. رشته به توان صفر برابر نال میشه و طولش صفره. صفر ضربدر k هم برابر صفر میشه. پس فرض اولیه درسته.

فرض میکنیم رابطه برای توان برابر n درست باشه.

حکم: باید رابطه برای توان n+1 هم درست باشه.

[tex]|w^{n+1}|=|w^n|+|w|=k*n+|w|=k*(n+1)[tex]

پس حکم ثابت شد.

یکبار دیگه هم برای توان ثابت مشابه همین رو حل میکنیم:
فرض اولیه توانمون n و طول رشته برابر صفره. دو طرف رابطه برابر صفر میشن.

فرض میکنیم به ازای طول برابر k رابطه صادق باشه.

حکم: باید رابطه برای طول k+1 هم درست باشه. یه پایانه به آخر رشته اضافه میکنید. پایانه هارو به انتهای رشته میبرید و طول رشته رو با طول پایانه ها جمع میکنید.

درود
خودم اینجوری نوشتم درسته؟

الف

S-> bS|aA
A->bA|lambda

ب

S-> aS|bS|aA
A->bA|lambda

---

واسه ج این و نوشتم

S->bS|aA|C
A->bA|aB|C
B->bA|aC|C
C->bC|lambda

---

ممنون از لطف همتون
واقعا یه تجربه عالی داشتم امشب تو این انجمن ولی افسوس که خیلی دیر اومدم ،

سعی میکنم از این به بعد همیشه اینجا باشم


سوال ۴

هر یک از زبانهای زیر را در نظر بگیرید ، گرامر یا زبانی را که تولید میکند بدست آوردید.

a) [tex]L={a^n b^m |n=>0,m>n }[/tex]

جواب
S->aAbb
A->aAb|B
B->bB|lambda



b) [tex]L={a^n b^2n |n=>0}[/tex]

جواب
S->aSbb|lambda


c) [tex]L={a^n 2|n=>1}[/tex]

جواب
S->aaaA
A->aA|lambda