۱- این دو زبان مستقل از متن قطعی است یا غیر قطعی:
{align=left] L={a^n b^j a^j b^n:n>=0,j>=0]
L={a^n b^j a^k b^l:n+j<=k+l}
[/align]
۲- آیا این زبان مستقل از متن است ؟ اگه هست قطعی است یا غیر قطعی؟:
L={a^n b^j: j<= n <= 2j-1}
۱-
الف )فکر کنم قطعی باشه چیزی که عدم قطعیت رو نشون بده وجود نداره.
یه سری a پوش میکنیم بعد هم یه سری b بعد به a که رسیدیم bها رو پاپ میکنیم که باید ابتدای پشته a باشه که b های ورودی رو به ازاش پاپ کنیم.
ب) این هم احتمالا قطعی است چون a,b های اولیه رو پوش میکنیم و بعد به ازای a,b های سری دوم پاپ میکنیم اگر پشته خالی شد حتی اگر هنوز ورودی تمام نشده رشته پذیرفته میشود.
۲- مستقل از متن است و فکر میکنم غیرقطعی باشد.چون اجتماع دو زبان مستقل از متن است و اگر گرامرش را بنویسید فکر میکنم مبهم باشد.
۱/ اولی مستقل از متن قطعی است دومی هم مستقل ازمتن قطعی است
۲/ مستقل از متن بودنش که حتمی است و غیر قطعی است چرا که به ازای هر دیدن a باید یک یا ۲ تا a در پشته پوش کند که مستقل از متن غیر قطعی میشه
درمورد زبان ۱-ب:
اگه دقت کنید میتونیم n+j=X و k+l=Y قرار بدبم. حالا به نظر من غیر قطعی میشه چون نمی تونیم بین a اولی و a دومی تمایز قائل شد. یعنی ممکنه X=0 باشد .
در اینجا ما چه جوری می تونیم متوجه بشیم که این a ایی که وارد پشته شد، کدوم a هست.
به نظر من که غیر قطعی است. لطفا اگه اشتباه می کنم کمکم کنید
مرسی
بله فکر کنم اگه k=0 باشه غیر قطعی میشه .