سلام دوستان
آیا زبان زیر خطی است؟زبان شامل رشته های w به شرط زیر
تعداد a+تعداد b=تعداد c
w متعلق به بستار ستاره a,b,c
(۰۹ خرداد ۱۳۹۳ ۰۸:۳۵ ب.ظ)negar.v نوشته شده توسط: سلام دوستانخیر مثلا برای استفاده از لم پامپینگ می توانید رشته ی [tex]W=a^mb^mc^{3m}a^m[/tex] در این صورت برای شکاندن رشته به زیر رشته های u,v,x,y,z برای این که شرط |uvyz|<=mمحقق شود مجبور است هم v هم y رو از a ها انتخاب کند و با تکرار این زیر رشته ها به تعداد i بار فقط تعداد a ها افزایش پیدا می کنه و تعداد بقیه ثابت می ماند پس رشته دیگر عضو زبان نخواهد بود
آیا زبان زیر خطی است؟زبان شامل رشته های w به شرط زیر
تعداد a+تعداد b=تعداد c
w متعلق به بستار ستاره a,b,c
سلام. وقت بخیر. با خطی نبودن زبان موافقم ولی به نظرم لم تزریق روش مناسبی نیست. ممنکه زبان خطی باشه ولی منظم نباشه.
(۱۱ خرداد ۱۳۹۳ ۰۳:۴۵ ب.ظ)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
(۱۱ خرداد ۱۳۹۳ ۱۱:۵۸ ب.ظ)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 ای پیدا کنیم که داخل زبان نباشد پس خطی نیست.
عذرخواهی میکنم. درمورد لم تزریق زبان خطی چیزی نشنیده بودم. لم تزریق رو فقط برای منظم و مستقل از متن استفاده میکردم.