صفحه‌ها: ۱ ۲
این زبان مستقل از متن است.حوصله نوشتن توضیحات ندارم ولی من خودم حداقل ۷ ای ۸ بار امسال که برای کنکور ارشد میخوندم حلش کردم و دقیقا تو کتاب پیتر لینز ترجمه صادق زاذه هستش.البته صادق زاده جامع ترین و بهترین ترجمه پیتر لینزه.
چون مطمئنم میگم.آخه خیلی خوب نظریه رو خواندم و چهار تا تو کنکور امسال زدم و هر چهار تاش درست بود.
از اونجایی که ماشین پشته ای توانایی محاسبه برابری w1 با w2 را ندارد. پس نمیتواند عدم برابری آنها را نیز محاسبه کند. پس این عدم توانایی ماشین پشته ای عدم مستقل از متن بودن را تایید میکند.
سلام. عدم برابری با برابر فرق میکنه. برای تشخیص عدم برابری اختلاف یک حرف کافیه. فقط کافیه یک حرف رو چک کنیم.
(۰۸ مرداد ۱۳۹۱ ۰۴:۱۶ ب.ظ)Jooybari نوشته شده توسط: سلام. عدم برابری با برابر فرق میکنه. برای تشخیص عدم برابری اختلاف یک حرف کافیه. فقط کافیه یک حرف رو چک کنیم.
دوست عزیز خوب شما به من بگو وقتی حرف اول w1 پایین پشته است و ما الان فقط به بالای پشته دسترسی داریم، چطور میتونیم چک کنیم حرف اول w1 با حرف اول w2 برابر هست یا نه؟
اگر باز هم میگید اشتباه میکنم، ماشینی طراحی کنید که عدم برابری رو بین دو رشته w1 و w2 رو چک کنه زبان هم همون w1Cw2 باشه.
من با اطمینان عرض میکنم که این زبان مستقل از متن نیست.
دوست عزیز گرامرشو در
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نوشته بودم. یک رشته بگید که جزء جواب باشه و این گرامر تولید نکنه و یا یک رشته بگید که گرامر تولید میکنه و جزء زبان نیست.
این اطمینان رو منم تا ۱۰ دقیقه قبل از امتحان پایانترم نظریه داشتم. سوال ۱ نظریه ما بود ثابت کنید این رشته مستقل از متن است. قبول دارم توضیحش خیلی سخته. ولی میشه یه dpda براش کشید.
توی pda این ماشین ما به کل رشته کاری نداریم. فقط یک حرف رو در حافظه محدودمون نگه میداریم و مکان اون حرف رو با پشته مشخص میکنیم. اگه بعد از c در همون مکان حرف مخالف حرف ذخیره شده بود به حالت پایانی میریم. چون نامعینه تمام حروف قبل از c رو چک میکنه. یک حالت هم میشه برای برابر نبودن طولها درنظر گرفت.
ببخشید شما از کجا میدونید کدوم حرف قراره متفاوت باشه که اونو تو حافظه موقت نگه دارید؟
من بعید میدونم، و ندیده مطمئن بودم گرامرت اشتباه است. الانم دیدم که رشته ای که توی زبان نیست رو تولید میکنه یعنی
S-->AD-->PAPD-->aAPD-->aaPD-->aaaD-->aaacB-->aaacPAP-->aaacaAP-->aaacaaP-->aaacaaa
که aaacaaa در زبان نیست.
اگر هم میگید که B میرود به PBP اونوقت من میخوام با این گرامر ، این رشته رو تولید کنم که نمیشه. bbbcbba
این رشته درون زبان هست اما گرامر شما نمیپذیردش.
من بی شک میگم که اشتباه میکنید.
گرامر خوبی بود.اما متاسفانه یه ایراد کوچیک داشت.
ببخشید مثل اینکه یه اشکال توی گرامر بود که رفع شد. باید مینوشتم B->PBP بجای B->PAP. کار این گرامر اینه که هسته یک طرف b و هسته طرف دیگر a باشه. وگرنه نیاز به تعریف B و D نبود. گرامرو چون پشت سرهم کپی میکردم یادم رفت جایگزین کنم.
رشته ای که شما نوشتید میشد S->AD->PAPD->aAPD->aaPD->aaaD->aaacB->aaacPAP->aaacaBP->aaacabP->aaacaba
رشته دوم: S->DA->Da->PDPa->PPDPPa->PPBcPPa->PPbcPPa->bbbcbba
این رشته رو قبول میکنه. حتی با گرامر غلط هم پذیرفته بود.
بله حق با شماست ، زبان مستقل از متنه. یه ماشین نا معین واسش نوشتم که جواب میده.
من عذر میخوام.هر چند که بازم فکر میکنم گرامر شما مشکل داره.
اگر مقدار اولیه پشته z باشه :
(q{0},a,\lambda )= (q{0},A)
(q{0},b,\lambda )= (q{0},B)
(q{0},\lambda,\lambda )= (q{1},\lambda)
(q{1},a,\lambda )= (q{1},\lambda)
(q{1},b,\lambda )= (q{1},\lambda)
(q{1},c,\lambda )= (q{2},\lambda)
(q{2},\lambda,A )= (q{3},\lambda)
(q{2},\lambda,B )= (q{4},\lambda)
(q{3},\lambda,Z )= (q{f},\lambda)
(q{3},b,Z )= (q{f},\lambda)
(q{3},b,B )= (q{3},\lambda)
(q{3},b,A )= (q{3},\lambda)
(q{3},a,A )= (q{3},\lambda)
(q{3},a,B )= (q{3},\lambda)
(q{4},a,Z )= (q{f},\lambda)
(q{4},\lambda,Z )= (q{f},\lambda)
(q{4},b,B )= (q{4},\lambda)
(q{4},b,A )= (q{4},\lambda)
(q{4},a,A )= (q{4},\lambda)
(q{4},a,B )= (q{4},\lambda)
هر کاری کردم نشد تو این فرمول new line کنم. مجبور شدم خودشو گذاشتم.
راستش اولین بار بود که گرامرشو نوشتم. قبلاً ماشینشو کشیده بودم که خیلی بزرگ شده بود. این گرامر رو از روی گرامر w1w2 که دو رشته اندازشون برابره و خودشون برابر نیستن نوشتم. فرقش با این زبان اینه که c نداره.
گرامر اون راحت تر بود. گرامرم اینجوری کار میکنه:
PR و LP برای تولید رشته هاییه که طول دو طرف حرف c برابر نیست. بقیشم دقیقاً مشابه همون w1w2 کار میکنه ولی در یکی از فضاهای بین حروف، حرف c رو قرار میده.
گرامر خوبی بود فقط یه جا ضعف داشت. اونم اینکه طول رشته ها برابر باشه اول و اخر دو تا هم با هم برابر باشه قبول نمیکنه.
چون فقط طول رشته و اول و آخر رشته رو چک میکنه.
امیدوارم که موفق باشید.
حرف شما رو قبول ندارم. چندتا رشته بگید که فکر میکنید گرامر قبول نمیکنه ولی جزء زبانه.
بله من اشتباه کردم. کامل توجه نکردم. درسته گرامر کاملا درسته.
نمیدونم چرا اینقدر رو این گرامر به اشتباه افتادم. کم توجهی کردم ببخشید.
برای این رشته:
S->AD->PAPD->babD->babPDP->babbDb->babbPDPb->babbaDab->babbaPDPab->babbabDbab->babbabcBbab->babbabcPBPbab->babbabcbbbbab
کافیه اون حرفی که اختلاف داره رو هسته درنظر بگیریم.
بله خودم متوجه شدم. عرض کردم که شما درست میفرمایید.
مشکل من این بود که فرضیه هام رو بدون آزمایش نوشتم.