۰
subtitle
ارسال: #۱
  
pumping lemma for Context Free Language
[/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
اگر لطف کنید به این سوالات جواب بدین ممنون می شوم
(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 میشه عدد نیست که ضرب بشه!)
W یک اشتقاق از زبانمون هست.یعنی از طریق گرامر به تک تک رشتهها میرسه.بعد شما رشته ای به عنوان "۱" اومدید به زبان اضافه کردید،رشته ای که حتی اگر در نظر بگیریم که به الفبامون اضافه کنیم اصلا توی زبان به کار نرفته و نباید برای ایجاد W استفاده بشه.(رشته Concat میشه عدد نیست که ضرب بشه!)
۰
ارسال: #۳
  
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 با هم برابره
اینو درست گفتم یا نه؟
یک سوال دیگر دارم:
برای 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 نوشته شده توسط: خیلی ممنون واقعا لطف کردین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 ثابت میشه که مستقل از متن نیست.
بقیه دوستان که توی این درس مسلطتر هستند اگر ایراد کار ایشون رو توضیح بدند خیلی ممنون میشم.
۰
ارسال: #۵
  
RE: pumping lemma for Context Free Language
بله حالا اشتباه شده بود.خوب من به این نتیجه رسیدم کهi=0 چون با گرفتن K1=k2در اخر دوباره به تعداد مساوی a,bمی رسیم و در ضمن با شرایط اولیه مان به تناقض نمی رسیم شرایط اولیه مان این بود: k1+k2+k3<=m>
,k1+k3<=1
اگر k1=k2باشد تناقضی ایجاد نمی کنه.یعنی اگر حتی بتونیم یک wپیداکنیم که در لم قابل قبول باشه ممکنه مستقل از متن باشه.
,k1+k3<=1
اگر k1=k2باشد تناقضی ایجاد نمی کنه.یعنی اگر حتی بتونیم یک wپیداکنیم که در لم قابل قبول باشه ممکنه مستقل از متن باشه.
۰
ارسال: #۶
  
pumping lemma for Context Free Language
کسی هست کمکی به من بکنه؟
زبان های مستقل از متن نسبت به معکوس کردن بسته هستن؟
زبان های مستقل از متن نسبت به معکوس کردن بسته هستن؟
۰
ارسال: #۷
  
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?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close