زبان مورد نظر مستقل از متن است
به ازای همه کاراکترهای w1 آنها را در پشته میگذاریم و بعد از رد کردن C به ازای هر کاراکتر از w2 اگر مساوی با بالای پشته بود پاپ می کنیم و اگر مساوی نبود به حالت پایانی میرویم

(۱۲ دى ۱۳۹۰ ۰۱:۳۰ ب.ظ)a_azarbarzin نوشته شده توسط:  زبان مورد نظر مستقل از متن است
به ازای همه کاراکترهای w1 آنها را در پشته میگذاریم و بعد از رد کردن C به ازای هر کاراکتر از w2 اگر مساوی با بالای پشته بود پاپ می کنیم و اگر مساوی نبود به حالت پایانی میرویم

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


البته کتاب پارسه این زبانو مستقل از متن نمیشناسه.

از نظر من زبان مستقل از متن نیست ولی اگر ممکن هست لطفا بگید از روی چه منبعی دارید این رو میگید
چون من تو کتاب لینز که نگاه کردم همچین بخشی وجود نداشت اگر ممکنه عکس اون قسمت یا لینکی ازش بگذارید تا بیشتر روش فکر کنیم

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

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

متن زبان اصلیشو ضمیمه کردم:

مستقل از متن هست تو کتاب سیپسر گفته می تونید ببینید.

دوستان اگه بخوان من میتونم ماشین پشته ای این زبان رو براتون بکشم.

مستقل از متن است و npda هست
چون ما هی پوش میکنیم تا یه ۱ i دلخواه حدس می زنیم که برابر نیست.همین

حتما مستقل از متن هست w1 در پشته push میشود به ازا a میتوان A و به ازا b میتوان B را وارد پشته کرد بعه رسیدن به عنصر جداکننده c آنگاه عمل pop شروع میشه و اگه w2 عناصرش با رشته w1 یکسان نبود به حالت پایانی میرویم لذا حتما مستقل از متن هستش

آقا یاسر رشته به فرم W1cW2 هست که W1 و W2 نباید مثل هم باشن. رشته دوم ریورس نیست. این ماشین نامعینه که باید بگیم یا طول این دو زیررشته برابر نیست و یا حداقل توی یه حرف اختلاف دارن.

(۲۲ خرداد ۱۳۹۱ ۰۱:۱۰ ق.ظ)Jooybari نوشته شده توسط:  آقا یاسر رشته به فرم W1cW2 هست که W1 و W2 نباید مثل هم باشن. رشته دوم ریورس نیست. این ماشین نامعینه که باید بگیم یا طول این دو زیررشته برابر نیست و یا حداقل توی یه حرف اختلاف دارن.

اره منم حرفت رو تایید میکنم منظور منم همین بود اره نامعینه

این چیزی که من توی پاسختون میبینم به نظرم صورت سوال رو درست نخوندین. پوش کردن ما فقط بخاطر پیداکردن مکان یک حرفه. توی پشته چه بجای a و چه b میتونیم ۱ پوش کنیم. بعدش فقط به یه حرف خاص توجه میکنیم. توضیح شما برای وقتیه که بجای پشته از صف استفاده کنیم. چون ما معکوس رشته رو که نمیخاهیم چک کنیم. خود رشته رو چک میکنیم.

(۲۲ خرداد ۱۳۹۱ ۰۱:۴۲ ق.ظ)Jooybari نوشته شده توسط:  این چیزی که من توی پاسختون میبینم به نظرم صورت سوال رو درست نخوندین. پوش کردن ما فقط بخاطر پیداکردن مکان یک حرفه. توی پشته چه بجای a و چه b میتونیم ۱ پوش کنیم. بعدش فقط به یه حرف خاص توجه میکنیم. توضیح شما برای وقتیه که بجای پشته از صف استفاده کنیم. چون ما معکوس رشته رو که نمیخاهیم چک کنیم. خود رشته رو چک میکنیم.

کتاب سودکمپ رو خوندی ؟ مثل حل این سوالات رو مثال داده بنده مثل اون عمل کردم و گفتم .

اما حرف شما درسته حل من میشه همون reverse .

حالا شرکتم شیفت شب برسم خونه حل کامل رو که مدنظرمه قرار میدم

(۱۱ دى ۱۳۹۰ ۰۶:۲۳ ب.ظ)reyhaneh64 نوشته شده توسط:  آیا زبان زیر مستقل از متن است؟
$L= w_{1}cw_{2}}: w_{1},w_{2}\epsilon \begin{Bmatrix}a,b \end{Bmatrix}^{*},w1 \neq w2$

انتهای کتاب جواب داده که هست( لازم به ذکره که حل تمرین ناقوس خلاف اینو گفته!!!)

دوستان من این درس رو با استاد ریاحی داشتم از خودشون پرسیدم گفت من کتاب حل تمرین رو موقعی که دانشجوی لیسانس بودم نوشتم و اینکه دیگه ویرایش نکردم ایشون هم گفتن این زبان مستقل از متن هست. و حل تمرین ایشون بعضی جاهاش کمو بیش اشکال دیده میشه و نظر خودشون هم هست که اشکال داره.

این زبان مستقل از متن است.حوصله نوشتن توضیحات ندارم ولی من خودم حداقل ۷ ای ۸ بار امسال که برای کنکور ارشد میخوندم حلش کردم و دقیقا تو کتاب پیتر لینز ترجمه صادق زاذه هستش.البته صادق زاده جامع ترین و بهترین ترجمه پیتر لینزه.
چون مطمئنم میگم.آخه خیلی خوب نظریه رو خواندم و چهار تا تو کنکور امسال زدم و هر چهار تاش درست بود.

از اونجایی که ماشین پشته ای توانایی محاسبه برابری 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
کافیه اون حرفی که اختلاف داره رو هسته درنظر بگیریم.

بله خودم متوجه شدم. عرض کردم که شما درست میفرمایید.
مشکل من این بود که فرضیه هام رو بدون آزمایش نوشتم.