سلام[/code]
زبان [tex]L={0^n1^f(n))|n\euro N}[/tex] رابرای تابعf:N->N در نظر بگیرید کدام گزینه نادرست است:
۱-f یک به یک،L منظم نیست
۲-برای برخی توابع f پوشا L میتواند مستقل ازمتن باشد
۳ زبان L میتواند محاسبه پذیر نباشد
۴-زبان L حداقل وابسته به متن است
جواب:۴
به ازای چه تابعی L محاسبه پذیر نیست؟
چرا هنوز کسی این سوال رو جواب نداده
سلام.
۱- اگه به ازای هر n یه (y=f(n جدا داشته باشیم، پس برای n نامحدود نیاز به مقایسه نامحدود داریم. پس منظم نیست.
۲- اگه f(n)=n باشد مستقل از متنه. پوشا هم هست.
۳- با عرض پوزش؛ محاسبه پذیر نمیدونم چیه!
۴- با توجه به گرامر گزینه ۲ غلطه. (مثال نقض)