[/align]L= a^(n )b^n(W=a^(m-k1 )(a^(k1 )^i) b^(k2 )( b^(m-k2)^ i
U=a^(m-k1 )
V=a^k1
X=1
y=b^(k2 )
z=b^(m-k2)
حالا اگر منk1+k2<=m >
فرض کردمi=0پس wعضو Lنیست ولی تو صفحه۲۴۱ لینز نوشته که از طریق لم برای زبان های مستقل از متن نمی توانیم رشته پیدا کنیم که عضوLنباشد.
چرا؟؟؟؟؟؟؟
L=a^(n )b^(m )c^m d^n
W=a^(n-k )((a^k)^ i )1((b^k)^i )(b^(m-k)) c^m d^n
حالا اگر من i=0بگیرم w عضوLنیست در صورتی که باید باشد چون اینم مستقل از متن هست؟
بعد توی کتاب گفته که v,yنباید رشته تهی باشد در موردxبگذاریم ۱اشکال دارد؟
میتواند باشد یا خیر؟Y=a^ b^c^n این برای V=1,y=a^k
اگر لطف کنید به این سوالات جواب بدین ممنون می شوم
معلومه که اشکال داره X=1 بگیرید!
W یک اشتقاق از زبانمون هست.یعنی از طریق گرامر به تک تک رشته‌ها میرسه.بعد شما رشته ای به عنوان "۱" اومدید به زبان اضافه کردید،رشته ای که حتی اگر در نظر بگیریم که به الفبامون اضافه کنیم اصلا توی زبان به کار نرفته و نباید برای ایجاد W استفاده بشه.(رشته Concat میشه عدد نیست که ضرب بشه!)
خیلی ممنون واقعا لطف کردین
یک سوال دیگر دارم:
برای L=a^n b^m c^m d^nمی توان
u=a^n b^m-k1-k2
v=b^k1
x=b^k3
y=c^k2
z=c^m-k2 d^n
خوب در آخر می گوییم k1=k2چون باید تعداد مساوی b,cتزریق شود؟چون تعداد b,c با هم برابره
اینو درست گفتم یا نه؟
(۲۹ شهریور ۱۳۸۹ ۱۰:۰۳ ب.ظ)tanin_2009 نوشته شده توسط: خیلی ممنون واقعا لطف کردینu را می خواستید بنویسید a^n b^m-k1-k3 .اشتباه تایپی بود دیگه؟
یک سوال دیگر دارم:
برای L=a^n b^m c^m d^nمی توان
u=a^n b^m-k1-k2
v=b^k1
x=b^k3
y=c^k2
z=c^m-k2 d^n
خوب در آخر می گوییم k1=k2چون باید تعداد مساوی b,cتزریق شود؟چون تعداد b,c با هم برابره
اینو درست گفتم یا نه؟
اگر اینطور باشه من نمی دونم ایراد کار از کجاست.از طرفی مطمئنم که این زبان مستقل از متن است چونکه میشه برای اون گرامر مستقل از متن نوشت از طرفی هم اشکالی توی حالتی که در نظر گرفتید نمی بینم و خیلی راحت با مساوی نگرفتن k1 و k2 و قرار دادن i=0 ثابت میشه که مستقل از متن نیست.
بقیه دوستان که توی این درس مسلط‌تر هستند اگر ایراد کار ایشون رو توضیح بدند خیلی ممنون میشم.
بله حالا اشتباه شده بود.خوب من به این نتیجه رسیدم کهi=0 چون با گرفتن K1=k2در اخر دوباره به تعداد مساوی a,bمی رسیم و در ضمن با شرایط اولیه مان به تناقض نمی رسیم شرایط اولیه مان این بود: k1+k2+k3<=m>
,k1+k3<=1
اگر k1=k2باشد تناقضی ایجاد نمی کنه.یعنی اگر حتی بتونیم یک wپیداکنیم که در لم قابل قبول باشه ممکنه مستقل از متن باشه.
کسی هست کمکی به من بکنه؟
زبان های مستقل از متن نسبت به معکوس کردن بسته هستن؟
فکر کنم در مستقل از متن قطعی آره ولی در مستقل از متن نه البته هردو در هم ریختی معکوس بسته هستند