زمان کنونی: ۱۰ اردیبهشت ۱۴۰۳, ۰۲:۳۱ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

pumping lemma for Context Free Language

ارسال:
  

tanin_2009 پرسیده:

Big Grin pumping lemma for Context Free Language

Huh[/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

اگر لطف کنید به این سوالات جواب بدین ممنون می شوم

۰
ارسال:
  

حامد پاسخ داده:

RE: pumping lemma for Context Free Language

معلومه که اشکال داره X=1 بگیرید!
W یک اشتقاق از زبانمون هست.یعنی از طریق گرامر به تک تک رشته‌ها میرسه.بعد شما رشته ای به عنوان "۱" اومدید به زبان اضافه کردید،رشته ای که حتی اگر در نظر بگیریم که به الفبامون اضافه کنیم اصلا توی زبان به کار نرفته و نباید برای ایجاد W استفاده بشه.(رشته Concat میشه عدد نیست که ضرب بشه!)

۰
ارسال:
  

tanin_2009 پاسخ داده:

RE: pumping lemma for Context Free Language

خیلی ممنون واقعا لطف کردین
یک سوال دیگر دارم:
برای 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 با هم برابره
اینو درست گفتم یا نه؟

ارسال:
  

حامد پاسخ داده:

RE: pumping lemma for Context Free Language

(۲۹ شهریور ۱۳۸۹ ۱۰:۰۳ ب.ظ)tanin_2009 نوشته شده توسط:  خیلی ممنون واقعا لطف کردین
یک سوال دیگر دارم:
برای 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 با هم برابره
اینو درست گفتم یا نه؟
u را می خواستید بنویسید a^n b^m-k1-k3 .اشتباه تایپی بود دیگه؟
اگر اینطور باشه من نمی دونم ایراد کار از کجاست.از طرفی مطمئنم که این زبان مستقل از متن است چونکه میشه برای اون گرامر مستقل از متن نوشت از طرفی هم اشکالی توی حالتی که در نظر گرفتید نمی بینم و خیلی راحت با مساوی نگرفتن k1 و k2 و قرار دادن i=0 ثابت میشه که مستقل از متن نیست.
بقیه دوستان که توی این درس مسلط‌تر هستند اگر ایراد کار ایشون رو توضیح بدند خیلی ممنون میشم.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

tanin_2009 پاسخ داده:

RE: pumping lemma for Context Free Language

بله حالا اشتباه شده بود.خوب من به این نتیجه رسیدم کهi=0 چون با گرفتن K1=k2در اخر دوباره به تعداد مساوی a,bمی رسیم و در ضمن با شرایط اولیه مان به تناقض نمی رسیم شرایط اولیه مان این بود: k1+k2+k3<=m>
,k1+k3<=1
اگر k1=k2باشد تناقضی ایجاد نمی کنه.یعنی اگر حتی بتونیم یک wپیداکنیم که در لم قابل قبول باشه ممکنه مستقل از متن باشه.

۰
ارسال:
  

ahmadnouri پاسخ داده:

pumping lemma for Context Free Language

کسی هست کمکی به من بکنه؟
زبان های مستقل از متن نسبت به معکوس کردن بسته هستن؟

۰
ارسال:
  

yasemi پاسخ داده:

pumping lemma for Context Free Language

فکر کنم در مستقل از متن قطعی آره ولی در مستقل از متن نه البته هردو در هم ریختی معکوس بسته هستند



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درخواست کتاب (Theory of formal languages with applications (Simovici Hera ۰ ۱,۶۱۰ ۰۹ مهر ۱۳۹۶ ۱۲:۱۲ ق.ظ
آخرین ارسال: Hera
  حل المساول کتاب (فووری) Speech and Language Processing, 2/E 2nd soosoo ۱ ۱,۷۰۰ ۱۵ خرداد ۱۳۹۶ ۰۹:۵۹ ق.ظ
آخرین ارسال: soosoo
  حل مسائل کتاب Concepts In Programming Languages - Mitchell Hera ۰ ۱,۹۷۶ ۲۲ آبان ۱۳۹۴ ۰۱:۴۱ ب.ظ
آخرین ارسال: Hera
  درخواست کتاب Design and implementation of programming languages e2000 ۰ ۱,۳۲۴ ۰۴ اسفند ۱۳۹۲ ۱۰:۲۹ ب.ظ
آخرین ارسال: e2000
  سئوال ۹۱ مدار منطقی برق ۹۱ در رابطه با ساده ترین پیاده سازی Hazard Free آرمین ۷ ۷,۴۱۲ ۱۱ آذر ۱۳۹۲ ۰۴:۳۸ ب.ظ
آخرین ارسال: آرمین
  Free Article's sahargh ۳۸ ۲۷,۵۷۰ ۰۸ فروردین ۱۳۹۱ ۰۳:۵۴ ق.ظ
آخرین ارسال: fotohireza
  Pumping Lemma - Ex4.13 Linz ۵۴m4n3h ۵ ۳,۳۳۳ ۳۱ شهریور ۱۳۸۹ ۱۲:۳۰ ق.ظ
آخرین ارسال: حامد

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close