درود
سوال هامو یکی یکی میپرسم
۱_به ازای تمام رشته های u , تمام n ها با اسقرا ثابت کنید درست است.
[tex]|u^n|= n|u|[/tex]
2_آیا زبان هایی وجود دارد که در آنها [tex]\bar{L*} =\bar{L}*[/tex] برقرار باشد چرا؟
سوال 1 شرمنده یکم طولانی میشه جوابش، منم فرصت ندارم.
فقط سوال دوم رو جواب میدم که خیر هیچ زبانی وجود نداره که توی این رابطه صدق کنه.
چون سمت راستی حتما لاندا داره(به دلیل ستاره روی کل عبارت) ولی در سمت چپی به هیچ عنوان امکان نداره که لاندا داشته باشه(به دلیل مکمل گرفتن از یه بستارستاره ای(بستار ستاره ای حتما شامل لانداست و وقتی مکمل بگیریم، حتما فاقد لاندا میشه) )
سلام. سوال اول:
طول رشته رو ثابت درنظر میگیریم:
فرض اولیه: فرض میکنیم اندازه رشته برابر k و توان هم برابر 0 باشه. رشته به توان صفر برابر نال میشه و طولش صفره. صفر ضربدر k هم برابر صفر میشه. پس فرض اولیه درسته.
فرض میکنیم رابطه برای توان برابر n درست باشه.
حکم: باید رابطه برای توان n+1 هم درست باشه.
[tex]|w^{n+1}|=|w^n|+|w|=k*n+|w|=k*(n+1)[tex]
پس حکم ثابت شد.
یکبار دیگه هم برای توان ثابت مشابه همین رو حل میکنیم:
فرض اولیه توانمون n و طول رشته برابر صفره. دو طرف رابطه برابر صفر میشن.
فرض میکنیم به ازای طول برابر k رابطه صادق باشه.
حکم: باید رابطه برای طول k+1 هم درست باشه. یه پایانه به آخر رشته اضافه میکنید. پایانه هارو به انتهای رشته میبرید و طول رشته رو با طول پایانه ها جمع میکنید.
ممنون از دوستان عزیز واقعن لطف کردید
3_گرامرهای روی [tex]\sum ={a,b}[/tex] بیابید که مجموعه های زیر را تولید میکند.
الف : تمای رشته هایی که فقط یک a دارد.
ب: تمامی رشته هایی که حداقل یک a دارد.
ج: تمامی رشته هایی که حداکثر 3 a دارد.
(04 بهمن 1391 11:55 ب.ظ)ms83 نوشته شده توسط: [ -> ]ممنون از دوستان عزیز واقعن لطف کردید
۳_گرامرهای روی [tex]\sum ={a,b}[/tex] بیابید که مجموعه های زیر را تولید میکند.
الف : تمای رشته هایی که فقط یک a دارد.
ب: تمامی رشته هایی که حداقل یک a دارد.
ج: تمامی رشته هایی که حداکثر ۳ a دارد.
الف:
S->BaB
B->bB|b
ج:
S->B|BaB|BaBaB|BaBaBaB
B->bB|b
درود
خودم اینجوری نوشتم درسته؟
الف
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
ممنون از لطف همتون
واقعا یه تجربه عالی داشتم امشب تو این انجمن ولی افسوس که خیلی دیر اومدم ،
سعی میکنم از این به بعد همیشه اینجا باشم
سوال 4
هر یک از زبانهای زیر را در نظر بگیرید ، گرامر یا زبانی را که تولید میکند بدست آوردید.
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