تالار گفتمان مانشت

سلام دوستان
آیا زبان زیر خطی است؟زبان شامل رشته های w به شرط زیر
تعداد a+تعداد b=تعداد c
w متعلق به بستار ستاره a,b,c

(09 خرداد 1393 08:35 ب.ظ)negar.v نوشته شده توسط: [ -> ]سلام دوستان
آیا زبان زیر خطی است؟زبان شامل رشته های w به شرط زیر
تعداد a+تعداد b=تعداد c
w متعلق به بستار ستاره a,b,c

خیر مثلا برای استفاده از لم پامپینگ می توانید رشته ی [tex]W=a^mb^mc^{3m}a^m[/tex] در این صورت برای شکاندن رشته به زیر رشته های u,v,x,y,z برای این که شرط |uvyz|<=mمحقق شود مجبور است هم v هم y رو از a ها انتخاب کند و با تکرار این زیر رشته ها به تعداد i بار فقط تعداد a ها افزایش پیدا می کنه و تعداد بقیه ثابت می ماند پس رشته دیگر عضو زبان نخواهد بود

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

(11 خرداد 1393 03:45 ب.ظ)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 ای پیدا کنیم که داخل زبان نباشد پس خطی نیست.

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

Sent from my ME172V using Tapatalk

(11 خرداد 1393 11:58 ب.ظ)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 ای پیدا کنیم که داخل زبان نباشد پس خطی نیست.

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