۰
subtitle
ارسال: #۱
  
تناقض در مستقل از متن به واسطه لم تزریق
با سلام مجدد
در صفحه ۱۷۵ گفته شده که
[tex]\widehat{L}=L\cup \left \{ a^nb^nc^n: n\geq 0 \right \}[/tex]
که میگه مستقل از متن هست
اما در صفحه ۱۸۳
[tex]L= \left \{ a^nb^nc^n: n\geq 0 \right \}[/tex]
گفته شده که این زبان مستقل از متن نیست
می دونیم چون زمانی که می خوایم c رو بخونیم نمی تونیم با b و a چکشون کنیم که تعدادشون یکیه بنابراین می گیم که مستقل از متن نیست
اما نمی دونم این قضیه چرا اینجوری هست
البته صفحه ۱۸۳ به واسطه لم تزریق اثبات شده که برام سوال هست
اونم اینه که در صورتی که vxy رو انتخاب کنیم به ازای هر a وbوc کلا m=1 هست در صورتی که می گه قابل قبول نیست و محدودیت ۲-۸ نمیزاره
در صورتی که اگه ما یکی a یکی b یکی c رو انتخاب کنیم در هر حال m برابر ۱ هست و شرط دچار مشکل نمیشه
نمی دونم چرا میگه نمیشه
لطفا راهنماییم کنید در این مورد
در صفحه ۱۷۵ گفته شده که
[tex]\widehat{L}=L\cup \left \{ a^nb^nc^n: n\geq 0 \right \}[/tex]
که میگه مستقل از متن هست
اما در صفحه ۱۸۳
[tex]L= \left \{ a^nb^nc^n: n\geq 0 \right \}[/tex]
گفته شده که این زبان مستقل از متن نیست
می دونیم چون زمانی که می خوایم c رو بخونیم نمی تونیم با b و a چکشون کنیم که تعدادشون یکیه بنابراین می گیم که مستقل از متن نیست
اما نمی دونم این قضیه چرا اینجوری هست
البته صفحه ۱۸۳ به واسطه لم تزریق اثبات شده که برام سوال هست
اونم اینه که در صورتی که vxy رو انتخاب کنیم به ازای هر a وbوc کلا m=1 هست در صورتی که می گه قابل قبول نیست و محدودیت ۲-۸ نمیزاره
در صورتی که اگه ما یکی a یکی b یکی c رو انتخاب کنیم در هر حال m برابر ۱ هست و شرط دچار مشکل نمیشه
نمی دونم چرا میگه نمیشه
لطفا راهنماییم کنید در این مورد
۰
ارسال: #۲
  
RE: تناقض در مستقل از متن به واسطه لم تزریق
الان کتاب در دسترسم نیست، اون زبان L که تو صفحه ۱۷۵ گفته شده چیه؟
برای اثبات با لم پامپینگ در این زبان
اگر [tex]w=a^{m}b^{m}c^{m}[/tex]
و [tex]vxy=a^{m}[/tex]
[tex]vy=a^{l}[/tex]
[tex]w_{0}=a^{m-l}b^{m}c^{m}[/tex]
که این رشته در زبان نیست.
همین یک نمونه برای اینکه بگیم زبان مستقل از متن نیست کافیه.
برای اثبات با لم پامپینگ در این زبان
اگر [tex]w=a^{m}b^{m}c^{m}[/tex]
و [tex]vxy=a^{m}[/tex]
[tex]vy=a^{l}[/tex]
[tex]w_{0}=a^{m-l}b^{m}c^{m}[/tex]
که این رشته در زبان نیست.
همین یک نمونه برای اینکه بگیم زبان مستقل از متن نیست کافیه.
Jooybari، در تاریخ ۱۷ تیر ۱۳۹۱ ۱۱:۲۶ ب.ظ برای این مطلب یک پانوشت گذاشته است:
برای لم تزریق باید تمام حالات vy با درنظرگرفتن uxz در رشته درنظر گرفته بشه. این زبان مستقل از متن نیست ولی این استدلال هم کافی نیست.
۰
ارسال: #۳
  
تناقض در مستقل از متن به واسطه لم تزریق
اگر بر فرض مثال مثلا a به توان n بود اون موقع چی میشد بگیم مستقل از متن هست؟
۰
ارسال: #۴
  
تناقض در مستقل از متن به واسطه لم تزریق
لطفا واضحتر بگین
همین الان هم a به توان n هست دیگه
اگه بگین اون L چیه شاید معلوم شد چرا این زبان مستقل از متن محسوب میشه.
همین الان هم a به توان n هست دیگه
اگه بگین اون L چیه شاید معلوم شد چرا این زبان مستقل از متن محسوب میشه.
۰
ارسال: #۵
  
RE: تناقض در مستقل از متن به واسطه لم تزریق
سلام دوباره
در باره مثال اول که شما نوشتید و در کتاب هم به عنوان زبان مستقل از متن معرفی شده، در انتهای توضیحات او بخش توضیح داده شده که در فصل بعدش(که لم پامپینگ رو آموزش داده) اثبات میکنه این زبان مستقل از متن نیست.
امیدوارم دیگه اشتباه یا ابهامی وجود نداشته باشه.
در باره مثال اول که شما نوشتید و در کتاب هم به عنوان زبان مستقل از متن معرفی شده، در انتهای توضیحات او بخش توضیح داده شده که در فصل بعدش(که لم پامپینگ رو آموزش داده) اثبات میکنه این زبان مستقل از متن نیست.
امیدوارم دیگه اشتباه یا ابهامی وجود نداشته باشه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close