صفحهها: ۱ ۲
پاسخ سوالات:
۱-ج
۲-د
۳-الف
۴-ج
۵-ج
۶-ب
اگه توضیحی نیاز داره سوال رو مشخص کنید.
۶و ۴ رو توضیح میدید؟
خب من بازم در جواب ب سوال ۶ مشکل دارم. به نظرم بازم ج می شه
چند سوال دیگه از نظریه. بنظرم برای سوالات تستی زیاد جالب نیست. بهتره علاوه بر جوابها استدلال خودتون رو هم بنویسید.
۱- چندتا از زبانهای زیر منظم هستند؟
[tex]L_1=\{a^nb^{2n 3};n\leq200\}[/tex]
[tex]L_2=\{a^ka^nb^m;k\geq 3,n\leq m\}[/tex]
[tex]L_3=\{w_1w_2|n_a(w_1)=n_b(w_2)\}[/tex]
[tex]L_2=\{a^ka^nb^m;k\geq 3,n\leq m\}[/tex]
[tex]L_3=\{w_1w_2|n_a(w_1)=n_b(w_2)\}[/tex]
الف) ۰
ب) ۱
ج) ۲
د) ۳
۲- کدام عبارت نادرست است؟
الف) برای هر عبارت منظم گرامر راست خطی وجود دارد.
ب) برای هر گرامر خطی میتوان یک dfa کشید.
ج) برای هر زبان که رشته های پذیرفته شده اش طول بزرگتر از M ندارند میتوان یک گرامر چپ خطی نوشت.
د) اگر گرامرهای G1 و G3 چپ خطی و G2 راست خطی باشند، میتوان گرامر [tex]S\to S_1S_2S_3[/tex] را بفرم راست خطی نوشت. ([tex]S_i[/tex] شروع گرامر [tex]G_i[/tex] است.)
۳- چند زبان زیر میتوانند منظم باشند؟
بستار ستاره L1 اگر L1 منظم نباشد.
L1.L1 اگر L1 منظم نباشد.
L1.L2 اگر L1 و L2 منظم نباشند.
L1-L2 اگر L1 و L2 منظم نباشند.
الف) ۱
ب) ۲
ج) ۳
د) ۴
سوال ۴ وقتی مقدار ۲na+3nb زوج میشه که فقط مقدار nb زوج باشه.
سوال ۶ فقط گزینه ۲ تمام رشته های زبان رو تولید میکنه. گزینه ج رشته های بدون a رو تولید نمیکنه. سوال زبانی رو میخاد که رشته های مشخص شده در صورت سوال رو تولید کنه. اگه رشته های بیشتر تولید کرد مشکلی نیست.
مثل اینکه جوابی درکار نیست. اگه پاسخی داشتید یا سوالی مونده با پیام خصوصی بفرستید. پاسخ هارو امشب قرار میدم. خدانگهدار.
جواب سوالات:
۱/ د
۲/ ب
۳/ د
من سوال اول رو مشکل دارم لطفا اگه میشه دوستان بخونن و بگن چرا L2 و L3 منظم هستند؟
سلام. برای L2 از سوال اول درنظر بگیرید n=0 و تمام aهارو جزء kتای اول بگیریم.. با این شرط عبارت منظم برای [tex]a^kb^m;k\geq 3 , b\geq 0[/tex] میشه [tex]aaaa^*b^*[/tex].
L3 هم زبانش سیکما استاره. یه رشته از a و b رو بنویسید. تعداد bهارو توی اون رشته بشمارید. حالا طول w1 رو به اندازه تعداد bها درنظر بگیرید. تعداد a های w1 با bهای w2 برابر میشه. هر رشته که درنظر بگیرید این مرز بین w1 و w2 وجود داره.
(۲۵ مهر ۱۳۹۱ ۱۱:۵۵ ب.ظ)Jooybari نوشته شده توسط: سلام. برای L2 از سوال اول درنظر بگیرید n=0 و تمام aهارو جزء kتای اول بگیریم.. با این شرط عبارت منظم برای [tex]a^kb^m;k\geq 3 , b\geq 0[/tex] میشه [tex]aaaa^*b^*[/tex].
L3 هم زبانش سیکما استاره. یه رشته از a و b رو بنویسید. تعداد bهارو توی اون رشته بشمارید. حالا طول w1 رو به اندازه تعداد bها درنظر بگیرید. تعداد a های w1 با bهای w2 برابر میشه. هر رشته که درنظر بگیرید این مرز بین w1 و w2 وجود داره.
سلام و ممنون بابت پاسختون,ولی من هنوزم ...:
در مورد L2 شما دارین یه رشته خاص از زبان بر میدارین و میگن منظمه ,حالا اگه کسی دوس داشت n=10 بزاره و رشته بشما بده میتونین aها رو تشخیص بدین ماله توان k هست یا توان n,ببینید شما یه زبان به من دادین و ادعا میکنین هر رشته ای که من اززین زبان به دلخواه خودم به شما دادم میتونین توسط یک ماشین متناهی accept کنین حالا شما منو نباید محدود کنین که n=0 قرار بدم.
در مورد L3 متوجه نشدم دلیلتون چیه لطفا یکم توضیح بیشتر یا با مثال بگین.ممنون بازم.
درمورد L2 گفتم n=0 درنظر بگیریم. چیزی که شما میگید درحالت عمومی درسته ولی برای این زبان، کلی ترین حالتش با n=0 بدست میاد. یعنی با افزایش این مقدار فقط جوابمون محدودتر میشه. ساده تر بگم «هر رشته ای که این زبان با هر n>0 میپذیره حتماً با n=0 میپذیره.» این جمله رو بررسی کنید.
L3 هم سوال کنکور بوده. نمودار (nb(w2)-na(w1 رو بر حسب طول رشته w1 بکشید. مقدار اولیه یک عدد نامنفی و مقدار نهایی یک عدد مثبت داره. با هر واحد افزایش طول w1 یک واحد از (nb(w2)-na(w1 کم میشه. پس حتماً محور رو قطع میکنه. یعنی (nb(w2)=na(w1 در یه نقطه ای صدق میکنه. رشته های مثال:
aababbbbababbaabba
این رشته ۱۰ تا b داره پس طول w1 میشه ۱۰: aababbbbab|abbaabba
bbabbbababbbabbbbabbbbaaaababaab
این رشته ۲۰ تا b داره پس طول w1 میشه ۲۰:bbabbbababbbabbbbabb|bbaaaababaab
(۲۶ مهر ۱۳۹۱ ۰۱:۴۴ ب.ظ)Jooybari نوشته شده توسط: درمورد L2 گفتم n=0 درنظر بگیریم. چیزی که شما میگید درحالت عمومی درسته ولی برای این زبان، کلی ترین حالتش با n=0 بدست میاد. یعنی با افزایش این مقدار فقط جوابمون محدودتر میشه. ساده تر بگم «هر رشته ای که این زبان با هر n>0 میپذیره حتماً با n=0 میپذیره.» این جمله رو بررسی کنید.
L3 هم سوال کنکور بوده. نمودار (nb(w2)-na(w1 رو بر حسب طول رشته w1 بکشید. مقدار اولیه یک عدد نامنفی و مقدار نهایی یک عدد مثبت داره. با هر واحد افزایش طول w1 یک واحد از (nb(w2)-na(w1 کم میشه. پس حتماً محور رو قطع میکنه. یعنی (nb(w2)=na(w1 در یه نقطه ای صدق میکنه. رشته های مثال:
aababbbbababbaabba
این رشته ۱۰ تا b داره پس طول w1 میشه ۱۰: aababbbbab|abbaabba
bbabbbababbbabbbbabbbbaaaababaab
این رشته ۲۰ تا b داره پس طول w1 میشه ۲۰:bbabbbababbbabbbbabb|bbaaaababaab
سلام. سوال یک، قسمت ۳، زبان منظمه؟
حد بین w1 و w2 رو چگونه مشخص کردی؟
بنظر من که این سوال جز گرامرهای وابسته به متن غیر قطعیه (push - down). چون حد فاصل بین دو تا رشته از یک زبان معلوم نیست.
اگه بیشتر در موردش توضیح بدی ممنون می شم.
(۲۶ مهر ۱۳۹۱ ۰۲:۵۷ ب.ظ)azad_ahmadi نوشته شده توسط:با نظر شما موافقم احتمال زیاد مستقل از متن غیر قطعیه.(26 مهر ۱۳۹۱ ۰۱:۴۴ ب.ظ)Jooybari نوشته شده توسط: درمورد L2 گفتم n=0 درنظر بگیریم. چیزی که شما میگید درحالت عمومی درسته ولی برای این زبان، کلی ترین حالتش با n=0 بدست میاد. یعنی با افزایش این مقدار فقط جوابمون محدودتر میشه. ساده تر بگم «هر رشته ای که این زبان با هر n>0 میپذیره حتماً با n=0 میپذیره.» این جمله رو بررسی کنید.
L3 هم سوال کنکور بوده. نمودار (nb(w2)-na(w1 رو بر حسب طول رشته w1 بکشید. مقدار اولیه یک عدد نامنفی و مقدار نهایی یک عدد مثبت داره. با هر واحد افزایش طول w1 یک واحد از (nb(w2)-na(w1 کم میشه. پس حتماً محور رو قطع میکنه. یعنی (nb(w2)=na(w1 در یه نقطه ای صدق میکنه. رشته های مثال:
aababbbbababbaabba
این رشته ۱۰ تا b داره پس طول w1 میشه ۱۰: aababbbbab|abbaabba
bbabbbababbbabbbbabbbbaaaababaab
این رشته ۲۰ تا b داره پس طول w1 میشه ۲۰:bbabbbababbbabbbbabb|bbaaaababaab
سلام. سوال یک، قسمت ۳، زبان منظمه؟
حد بین w1 و w2 رو چگونه مشخص کردی؟
بنظر من که این سوال جز گرامرهای وابسته به متن غیر قطعیه (push - down). چون حد فاصل بین دو تا رشته از یک زبان معلوم نیست.
اگه بیشتر در موردش توضیح بدی ممنون می شم.
این سوال کنکور ۹۰ بوده که اونجا اسمی از منظم نبرده و با توجه به پاسخنامه گفته مستقل از متنه این زبان هر چند که زبانهای منظم زیر مجموعه زبانهای مستقل از متن هستند.ولی به هر حال جناب جویباری این زبان یه زبان غیر متناهی هستش که برای اینکه تعداد b ها بشمارین باید تا آخر زبان رو طی کنین ,بازم دقیق نمی دونم من نتونستن ماشینش رو بکشم اگه کسی از دوستان تونست ماشینش رو بکشه همه چیز حل میشه.
هر چند در کتاب آقای سهرابی(پوران) گفته اصلا این زبان مستقل از متن نیس و گفته میشه با لم تزریق اینو ثابت کرد!!!!
L3 منظمه. چندنفر از دوستان چندبار با پیام خصوصی همین زبان هارو از من پرسیدن. زبان سوال همون سیکما استاره. اینی که گفتم باید تعداد bهارو بشماریم برای مشخص کردن مرزه. وگرنه لزومی به مشخص کردن مرز برای اثبات عضو زبان بودن رشته توسط ماشین نیست. اگه قبول ندارید یه رشته مثال بزنید که عضو زبان نباشه.
درسته. حق با آقای جویباری هست. ممنون سوال خوبی بود.
توضیح بیشتر در مورد سوال یک قسمت سه.
------------------------------------------------
ببینید اصل زبان همون L* هست که همین باعث منظم بودن زبان میشه. این از این.
شما هر دنباله ای از aوb رو اگه بنویسید، اولا w1 رو برابر کل تعداد bهای کل رشته درنظربگیرید. حالا طول w1 هرچقدر باشه اون رو از کل رشته از چپ به راست جدا می کنیم. این قسمت میشه w1؛ هرتعداد aوb که مونده باشه میشه w2.
حالا تعداد aهای w1 با تعداد bهای w2 برابره. (سوال در حد یه معجزه س
).مثال:
رشته abaabababbaababb رو در نظر بگیر. تعداد bها که گفتیم همون w1 میشه. پس w1 = 8.
حالا به تعداد ۸ تا از رشته اصلی رو از چپ به راست جدا کن. میشه abaababa که میشه همون w1.
حالا w1 = abaababa و w2 = bbaababb (توجه کن که w2 ادامه رشته بعد از w1 است).
حالا به طرز معجزه اسایی تعداد aهای w1 برابر bهای w2 است.
برای هر رشته ی دیگری هم همین روال رو ادامه بدی درسته.
پس زبان اصلی همون L* بوده که زبانی منظم است.
موفق باشی.
-----------
ممنون از آقای جویباری.