سلام. وقت بخیر. با خطی نبودن زبان موافقم ولی به نظرم لم تزریق روش مناسبی نیست. ممنکه زبان خطی باشه ولی منظم نباشه.

(۱۱ خرداد ۱۳۹۳ ۰۳:۴۵ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقت بخیر. با خطی نبودن زبان موافقم ولی به نظرم لم تزریق روش مناسبی نیست. ممنکه زبان خطی باشه ولی منظم نباشه.

سلام منظورم لم پامپینگ مخصوص زبان های خطی بود این لم به شرح زیر است:
فرض کنید زبان L یک زبان خطی نامتناهی باشد در این صورت عدد m ای وجود دارد که به ازای هر رشته از زبان که طول آن |w|>=m باشد می توان آن را رشته را طوری به زیر رشته های u,v,x,y,z شکاند که w=uvxyz و |uvyz|<=m , |vy|>=1 در حالیکه
w_i=uv^i xy^i z
به ازای تمام مقادیر i داخل زبان باشد.
پس اگر زبانی این ویژگی را نداشت و توانستیم w_i ای پیدا کنیم که داخل زبان نباشد پس خطی نیست.

(۱۱ خرداد ۱۳۹۳ ۱۱:۵۸ ب.ظ)fatemeh69 نوشته شده توسط:  سلام منظورم لم پامپینگ مخصوص زبان های خطی بود این لم به شرح زیر است:
فرض کنید زبان L یک زبان خطی نامتناهی باشد در این صورت عدد m ای وجود دارد که به ازای هر رشته از زبان که طول آن |w|>=m باشد می توان آن را رشته را طوری به زیر رشته های u,v,x,y,z شکاند که w=uvxyz و |uvyz|<=m , |vy|>=1 در حالیکه
w_i=uv^i xy^i z
به ازای تمام مقادیر i داخل زبان باشد.
پس اگر زبانی این ویژگی را نداشت و توانستیم w_i ای پیدا کنیم که داخل زبان نباشد پس خطی نیست.

عذرخواهی میکنم. درمورد لم تزریق زبان خطی چیزی نشنیده بودم. لم تزریق رو فقط برای منظم و مستقل از متن استفاده میکردم.

من لم پامپینگ برای زبان های خطی رو از جزوه دکتر کارگهی یاد گرفته بودم اما سر جلسه آزمون آزاد کلا یادم رفت که ازش استفاده کنم،
ممنون از پاسختون

Sent from my ME172V using Tapatalk