سوال از بخش تصمیم پذیری - نسخه‌ی قابل چاپ

سوال از بخش تصمیم پذیری - arshad90 - 10 دى ۱۳۸۹ ۰۱:۴۴ ب.ظ سوالات از کتاب محبوب پیتر لینز هست. همینجا تایپ می کنم تا زحمت دانلود سوال رو نکشید. سوال اول) گرامر مستقل از متن G1 و گرامر منظم G2 را در نظر بگیرید، آیا مساله L(G1) (اشتراک) L (G2) = تهی تصمیم پذیره؟ سوال دوم) گرامر منظم G1 و گرامر G2 را در نظر بگیرید. آیا مساله L(G1) = L(G2) در هر یک از شرایط زیر تصمیم پذیره؟ الف) G2 نامحدود باشه. ب) G2 مستقل از متن باشه. ج) G2 منظم باشه. سوال سوم) ساختار و کارایی الگوریتمی که زبان L را می پذیرد در هر یک از انواع ماشین تورینگ های زیر را تعیین کنید. L= {www‌: w ozve {a,b}} ۱) با ماشین تورینگ استاندارد ۲) ماشین تورینگ قطعی دونواره ۳) ماشین تورینگ غیرقطعی تک نواره ۴) ماشین تورینگ غیرقطعی دونواره منتظر جواباتون هستم.[/b]

سوال از بخش تصمیم پذیری - sepid - 11 دى ۱۳۸۹ ۰۱:۱۷ ق.ظ سلام ۱/ جواب بله است. چون حاصل اشتراک یک زبان CF است . حال کافی است برای این زبان بررسی کنیم ببینیم تهی است یا نه که برای این کار باید ببینیم متغیر شروع زبان حاصل یک متغیر مفید است یا خیر. ۲/برای بررسی برابر بودن دو زبان باید تهی=L2-L1 شود یعنی تهی =متممL2∩L1 شود. الف)جواب خیر است.زیرا حاصل اشتراک برابر یک زبان نامحدود است و برای این زبان نیز مساله برابر تهی بودنش تصمیم ناپذیره. ب)جواب بله است.چون حاصل اشتراک زبان مستقل از متن است . ج)بله. ۳/اینو دقیق نمیدونم.ولی فک کنم با ماشین تورینگ قطعی دو نواره زمانش از همش کمتر میشه.