۰
subtitle
ارسال: #۱
چند سوال در مورد نوع زبانها
دلیل هرکدام را بیان کنید:
۱-زبان {U W W^R V} L1=,و L2={U^n W V^n W^R} منظم است؟
۲-زبان {WW} CF است؟
۳-{W|n(a) W mod 2 < n(b) W mod 3 } ، CF است؟
۴- DCFها تحت معکوس بسته هستند یا متمم؟ آیا مثال زیر می تواند مثال نقض این باشد که نسبت به متمم بسته هستند:
L={a^n b^n} DCF
M(L) ={n(a)(W)<> n(b)(W)} : DCF
۱-زبان {U W W^R V} L1=,و L2={U^n W V^n W^R} منظم است؟
۲-زبان {WW} CF است؟
۳-{W|n(a) W mod 2 < n(b) W mod 3 } ، CF است؟
۴- DCFها تحت معکوس بسته هستند یا متمم؟ آیا مثال زیر می تواند مثال نقض این باشد که نسبت به متمم بسته هستند:
L={a^n b^n} DCF
M(L) ={n(a)(W)<> n(b)(W)} : DCF
۰
ارسال: #۲
چند سوال در مورد نوع زبانها
۱/L1 منظم هست ولی L2 نه.
۲/خیر CF نیست چون با یک پشته نمیتونیم پیادش کنیم. در واقع باید عناصر w رو کامل داشته باشیم تا بتونیم w بعدی رو چک کنیم ولی پشته معکوس رشته رو میتونه در بیاره نه خودش رو یعنی اگر حافظه صف بود اون موقع میتونستیم.
۳/ منظم هست پس مستقل از متن هم هست.
۴/ زبانهای قطعی تحت معکوس و متمم بسته نیست.
اثباتش برای متمم همون اثبات ساختاری هست که برای زبانهای مستقل از متن داشتیم.
اگر کتاب لینز رو دارید همه سوالات رو توش حل کرده یعنی یا تمرینش هست یا مثال کتاب.
۲/خیر CF نیست چون با یک پشته نمیتونیم پیادش کنیم. در واقع باید عناصر w رو کامل داشته باشیم تا بتونیم w بعدی رو چک کنیم ولی پشته معکوس رشته رو میتونه در بیاره نه خودش رو یعنی اگر حافظه صف بود اون موقع میتونستیم.
۳/ منظم هست پس مستقل از متن هم هست.
۴/ زبانهای قطعی تحت معکوس و متمم بسته نیست.
اثباتش برای متمم همون اثبات ساختاری هست که برای زبانهای مستقل از متن داشتیم.
اگر کتاب لینز رو دارید همه سوالات رو توش حل کرده یعنی یا تمرینش هست یا مثال کتاب.
۰
۰
ارسال: #۴
چند سوال در مورد نوع زبانها
البته در مورد ۲ هم این که الفبای زبان چی باشه مهمه مثلاً اگه تک الفبایی باشه اون موقعه منظم میشه و رشته‌های با طول زوج خواهد بود ولی اگر بیش از یک الفبا داشته باشه مستقل از متن است
ارسال: #۵
RE: چند سوال در مورد نوع زبانها
(۰۶ بهمن ۱۳۸۹ ۰۱:۴۲ ق.ظ)hatami84 نوشته شده توسط: البته در مورد ۲ هم این که الفبای زبان چی باشه مهمه مثلاً اگه تک الفبایی باشه اون موقعه منظم میشه و رشته‌های با طول زوج خواهد بود ولی اگر بیش از یک الفبا داشته باشه مستقل از متن است
آره برای تک الفبایی حرفتون درسته ولی برای الفبای بیشتر از یکی مستقل از متن نمیشه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close