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

دلیل هرکدام را بیان کنید:
1-زبان {U W W^R V} L1=,و L2={U^n W V^n W^R} منظم است؟
2-زبان {WW} CF است؟
3-{W|n(a) W mod 2 < n(b) W mod 3 } ‌، CF است؟
4- DCF‌ها تحت معکوس بسته هستند یا متمم؟ آیا مثال زیر می تواند مثال نقض این باشد که نسبت به متمم بسته هستند:
L={a^n b^n} DCF
M(L) ={n(a)(W)<> n(b)(W)} ‌: DCF

1.L1 منظم هست ولی L2 نه.
2.خیر CF نیست چون با یک پشته نمیتونیم پیادش کنیم. در واقع باید عناصر w رو کامل داشته باشیم تا بتونیم w بعدی رو چک کنیم ولی پشته معکوس رشته رو میتونه در بیاره نه خودش رو یعنی اگر حافظه صف بود اون موقع میتونستیم.
3. منظم هست پس مستقل از متن هم هست.
4. زبانهای قطعی تحت معکوس و متمم بسته نیست.
اثباتش برای متمم همون اثبات ساختاری هست که برای زبانهای مستقل از متن داشتیم.
اگر کتاب لینز رو دارید همه سوالات رو توش حل کرده یعنی یا تمرینش هست یا مثال کتاب.

کاش از TEX استفاده میکردین واسه نوشتن سوالها!

البته در مورد 2 هم این که الفبای زبان چی باشه مهمه مثلاً اگه تک الفبایی باشه اون موقعه منظم میشه و رشته‌های با طول زوج خواهد بود ولی اگر بیش از یک الفبا داشته باشه مستقل از متن است

(06 بهمن 1389 01:42 ق.ظ)hatami84 نوشته شده توسط: [ -> ]البته در مورد 2 هم این که الفبای زبان چی باشه مهمه مثلاً اگه تک الفبایی باشه اون موقعه منظم میشه و رشته‌های با طول زوج خواهد بود ولی اگر بیش از یک الفبا داشته باشه مستقل از متن است

آره برای تک الفبایی حرفتون درسته ولی برای الفبای بیشتر از یکی مستقل از متن نمیشه.