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

مستقل از متن هست؟ a^nb^mc^n , m>n>0

ارسال:
  

lonelyforever پرسیده:

مستقل از متن هست؟ a^nb^mc^n , m>n>0

{a^{n}b^{m}c^{n} | n>=m>= 0}



نمی دونم واقعا اما فکر می کنم میشه اول به ازای n ‌، n تا بزاری تو پشته‌، بعد به ازای هر b اون متغیری که گذاشتی تو پشته بخونی و باز همون رو پوش کنی. اگه تعداد b بیشتر بشه دیگه به جای میرسه که نمی تونه چیزی رو پاپ کنه پس ادامه کار قطع میشه. اگه هم کمتر از تعداد n باشه به سلامت میره رو c و به ازاری هر c یه متغیر پاپ میکنه و پشته هم در انتها خلی میشه.
اما میگن این مستقل از من نیست.

{a^{n}b^{m}c^{n} | m> =n>= 0}


میشه یکی توضیح بده لطفا فرق این دوتا چیه و کدومش مستقل هست و کدومش نیست؟
با تشکر.

۰
ارسال:
  

Jooybari پاسخ داده:

من میگم مستقل از متن هست نظر شما چیه؟

هیچکدوم مستقل از متن نیستن. جفتشو میشه با لم تزریق رد کرد. یا باید تعداد cها رو با aها برابر کنیم یا شرط تعداد b رو درنظر بگیریم.
توی استدلالتو گفتین "دوباره همون متغیر رو پوش کنیم" اگه اینکارو بکنیم که تعداد aهای توی پشته با خوندن b تغییر نمیکنه و نمیتونیم بین m و n مقایسه داشته باشیم.
رشته a^nb^nc^n رو درنظر بگیرید که توی هردو زبان پذیرفتست. با لم تزریق میشه ثابت کرد مستقل از متن نیست. اگه vy فقط جزء aها یا cها باشه که تعدادشون به ازای i=2 برابر نیست. اگه فقط جزء bها باشه که با قراردادن i=0,2 مثال نقض داریم. واگه بینشون باشه یکی از دوحالت قبل پیش میاد.

۰
ارسال:
  

mohammad_1366 پاسخ داده:

من میگم مستقل از متن هست نظر شما چیه؟

two terms are not a context free language



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سلام آیا اینجا کسی رشتش کامپیوتر هست؟ parisa1140 ۲ ۳,۸۷۳ ۱۹ بهمن ۱۳۹۹ ۱۱:۰۶ ب.ظ
آخرین ارسال: farsamw
  بعد ۶ سال اومدم، ارشد مهندسی کامپیوتر کسی هست؟؟ seyed_eng ۷ ۵,۵۱۴ ۱۱ آبان ۱۳۹۹ ۰۷:۴۷ ق.ظ
آخرین ارسال: iraj.leo
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۲۰,۹۶۰ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
Smile چطور امکان قبولی در رشته رایانش امن هست؟ نوشتن ۲ ۳,۹۶۸ ۰۷ تیر ۱۳۹۸ ۱۰:۳۲ ق.ظ
آخرین ارسال: نوشتن
  شرکت در آزمون دکتری در دو رشته همزمان امکانپذیر هست؟ saharomidi ۳ ۵,۴۲۶ ۲۴ فروردین ۱۳۹۸ ۰۳:۱۹ ق.ظ
آخرین ارسال: saharomidi
  گرامر مستقل از متن Sanazzz ۴ ۴,۸۶۳ ۱۲ دى ۱۳۹۷ ۰۹:۵۹ ب.ظ
آخرین ارسال: Sanazzz
  متن ایمیل برای نویسنده مقاله Iran2014 ۲ ۳,۱۲۳ ۱۰ مهر ۱۳۹۷ ۰۹:۱۵ ب.ظ
آخرین ارسال: Iran2014
  کنکور ارشد مجموعه مهندسی کامپیوتر با لیسانسی که گرایشش it هست ؟ mrhosseini97 ۱ ۲,۳۵۹ ۰۵ مهر ۱۳۹۷ ۰۳:۳۳ ب.ظ
آخرین ارسال: mahatasa
  کنکور ارشد مجموعه مهندسی کامپیوتر با لیسانسی که گرایشش it هست ؟ mrhosseini97 ۱ ۲,۳۹۶ ۰۴ مهر ۱۳۹۷ ۱۱:۲۷ ب.ظ
آخرین ارسال: mrhosseini97
  از دانشجویان پروفسور نوابی کسی اینجا هست؟ ah_bzk ۵ ۵,۶۵۸ ۱۳ خرداد ۱۳۹۷ ۱۱:۴۴ ب.ظ
آخرین ارسال: ah_bzk

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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