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

تناقض در مستقل از متن به واسطه لم تزریق

ارسال:
  

masoudkhan پرسیده:

تناقض در مستقل از متن به واسطه لم تزریق

با سلام مجدد
در صفحه ۱۷۵ گفته شده که
[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 برابر ۱ هست و شرط دچار مشکل نمیشه
نمی دونم چرا میگه نمیشه
لطفا راهنماییم کنید در این مورد

۰
ارسال:
  

behdad پاسخ داده:

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]

که این رشته در زبان نیست.
همین یک نمونه برای اینکه بگیم زبان مستقل از متن نیست کافیه.
Jooybari، در تاریخ ۱۷ تیر ۱۳۹۱ ۱۱:۲۶ ب.ظ برای این مطلب یک پانوشت گذاشته است:

برای لم تزریق باید تمام حالات vy با درنظرگرفتن uxz در رشته درنظر گرفته بشه. این زبان مستقل از متن نیست ولی این استدلال هم کافی نیست.

۰
ارسال:
  

masoudkhan پاسخ داده:

تناقض در مستقل از متن به واسطه لم تزریق

اگر بر فرض مثال مثلا a به توان n بود اون موقع چی میشد بگیم مستقل از متن هست؟

۰
ارسال:
  

behdad پاسخ داده:

تناقض در مستقل از متن به واسطه لم تزریق

لطفا واضح‌تر بگین
همین الان هم a به توان n هست دیگه

اگه بگین اون L چیه شاید معلوم شد چرا این زبان مستقل از متن محسوب میشه.

۰
ارسال:
  

behdad پاسخ داده:

RE: تناقض در مستقل از متن به واسطه لم تزریق

سلام دوباره
در باره مثال اول که شما نوشتید و در کتاب هم به عنوان زبان مستقل از متن معرفی شده، در انتهای توضیحات او بخش توضیح داده شده که در فصل بعدش(که لم پامپینگ رو آموزش داده) اثبات میکنه این زبان مستقل از متن نیست.
امیدوارم دیگه اشتباه یا ابهامی وجود نداشته باشه.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۲۱,۱۷۵ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
  گرامر مستقل از متن Sanazzz ۴ ۴,۹۲۸ ۱۲ دى ۱۳۹۷ ۰۹:۵۹ ب.ظ
آخرین ارسال: Sanazzz
  متن ایمیل برای نویسنده مقاله Iran2014 ۲ ۳,۱۵۰ ۱۰ مهر ۱۳۹۷ ۰۹:۱۵ ب.ظ
آخرین ارسال: Iran2014
  متن کاوی zorro ۰ ۱,۷۱۰ ۲۸ بهمن ۱۳۹۶ ۰۷:۲۸ ب.ظ
آخرین ارسال: zorro
  منظور این متن در آمار چیست؟ H-Arshad ۰ ۱,۴۰۳ ۲۶ مهر ۱۳۹۶ ۰۳:۲۶ ق.ظ
آخرین ارسال: H-Arshad
  دیتاست برای بازیابی اطلاعات مانند تصویر و متن در شبکه های اجتماعی minamm ۰ ۱,۸۸۸ ۱۷ اردیبهشت ۱۳۹۶ ۱۰:۲۲ ق.ظ
آخرین ارسال: minamm
  حساس به متن و مستقل از متن kilookiloo ۲ ۲,۵۶۷ ۰۶ اردیبهشت ۱۳۹۶ ۰۷:۴۱ ق.ظ
آخرین ارسال: kilookiloo
  تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی AZ_AMIR ۲ ۳,۰۱۷ ۰۳ اردیبهشت ۱۳۹۶ ۰۷:۵۳ ب.ظ
آخرین ارسال: AZ_AMIR
  تشخیص زبان مستقل ازمتن قطعی mzha ۲ ۱,۹۰۷ ۲۲ دى ۱۳۹۵ ۱۰:۱۷ ب.ظ
آخرین ارسال: mzha
  کمک در پردازش متن با پایتون mariyG ۵ ۳,۷۲۲ ۱۹ آذر ۱۳۹۵ ۱۱:۲۹ ب.ظ
آخرین ارسال: mariyG

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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