با عرض سلام خسته نباشید به همه شما
گرامر زیر چه زبانی را تولید می کند؟
AB|λ → S
aB→A
Sb→B
1)همه رشته هایی که تعداد aها برابر تعداد b هاباشد
2)همه رشته هایی که بصورت a^n b^n
3) همه رشته هایی که بصورت a^n b^2n
4)همه رشته هایی که در ان تعداد aها برابرنصف تعدادb هاباشد
جواب زده گزینه چهار ولی نفهمیدم چطوری
استدلالش بخاطر این فرمول که خودش گفته باید به یاد داشته باشید
|S|=|A|+|B|=a+|B´|+|S´|+b=|a|+|S̋|+|b|+|S´|+|b|
با تشکر
فکر میکنم این سوالو میشه ساده تر این جوابی که گذاشتید هم حل کرد
شما بجای A قرار بده aB (رشته ای که تولید میکنه)
گرامر تبدیل میشه به
aBB|λ → S
حالا بجای B هم قرار بده Sb پس داریم
aSbSb|λ → S
مشخصه که تعداد b دوبرابر a هست
من که از ایین فرمولی که شما نوشتید سردر نیاوردم
سلام. گرامری که خانم narges_r نوشتند درسته. گرامر رو می نویسم:
[tex]S\to AB|\lambda[/tex]
[tex]A\to aB[/tex]
[tex]B\to Sb[/tex]
حالا A رو حذف می کنیم.
[tex]S\to aBB|\lambda[/tex]
[tex]B\to Sb[/tex]
و با حذف B داریم:
[tex]S\to aSbSb|\lambda[/tex]
جواب توی هیچ گزینه ای نیست. تعداد b ها دوبرابر a ها هست ولی گزینه 4 رشته هایی مثل bba رو شامل میشه که گرامر تولید نمیکنه.
رشته ی ababbb طبق مشتقات زیر بدست میاد:
AB
A=aB
B=Sb
پس
A=aSb
-----
پس
AB=
aSbSb
=
abABb
abaSbSbb
S=null
پس
ababbb
----
پس تا اینجا گزینه های 1و2و3 رد میشن
---
گزینه ی 4 هم نمیشه گفت درست هست زیرا الزاما رشته های تولیدی با a شروع میشن و مثلا bba رو نمیشه تولید کرد.
ولی اگه سخت نگیریم تقریبا همون 4 درسته
(09 بهمن 1391 01:31 ق.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. گرامری که خانم narges_r نوشتند درسته. گرامر رو می نویسم:
[tex]S\to AB|\lambda[/tex]
[tex]A\to aB[/tex]
[tex]B\to Sb[/tex]
حالا A رو حذف می کنیم.
[tex]S\to aBB|\lambda[/tex]
[tex]B\to Sb[/tex]
و با حذف B داریم:
[tex]S\to aSbSb|\lambda[/tex]
جواب توی هیچ گزینه ای نیست. تعداد b ها دوبرابر a ها هست ولی گزینه ۴ رشته هایی مثل bba رو شامل میشه که گرامر تولید نمیکنه.
درود بر شما درسته