صفحه‌ها: ۱ ۲
آیا زبان زیر مستقل از متن است؟
[tex]L= w_{1}cw_{2}}: w_{1},w_{2}\epsilon \begin{Bmatrix}a,b \end{Bmatrix}^{*},w1 \neq w2[/tex]
انتهای کتاب جواب داده که هست( لازم به ذکره که حل تمرین ناقوس خلاف اینو گفته!!!)
توضیحات کتاب:
یک npda ایجاد میکنیم، که تا مقدار k را بشمارد(با گذاشتن k علامت روی پشته )و به خاطر سپردن uام کاراکتر و سپس بررسی کردن uام کاراکتر در w2 و اگر این، با کاراکتر حفظ شده برابر نباشد، رشته پذیرفته میشود اگر wعضو L باشد باید uی وجود داشته باشد که این اتفاق بیفتد و npda به طور نامعین، k را انتخاب میکند.
مفهوم این توضیحاتو برای پیاده سازی روی ماشین متوجه نمیشم و نمیدونم چطور پیادش کنم
ممنون میشم یاری کنید.
زبان مورد نظر مستقل از متن است
به ازای همه کاراکترهای w1 آنها را در پشته میگذاریم و بعد از رد کردن C به ازای هر کاراکتر از w2 اگر مساوی با بالای پشته بود پاپ می کنیم و اگر مساوی نبود به حالت پایانی میرویم
(۱۲ دى ۱۳۹۰ ۰۱:۳۰ ب.ظ)a_azarbarzin نوشته شده توسط: زبان مورد نظر مستقل از متن استدر این صورت فقط رشته هایی پذیرفته میشن که معکوس زبان w1 هستن.
به ازای همه کاراکترهای w1 آنها را در پشته میگذاریم و بعد از رد کردن C به ازای هر کاراکتر از w2 اگر مساوی با بالای پشته بود پاپ می کنیم و اگر مساوی نبود به حالت پایانی میرویم
در صورتیکه عدم برابری دو رشته، فقط به دلیل معکوس بودن نیست، ممکنه به خاطر عدم برابری طول باشه یا عدم تطابق حرف اول یا....
همه اینا باید بررسی بشن.
سوالم اینه با این الگوریتمی که کتاب عنوان کرده چطور میشه این کارو در ماشین پشته ای انجام داد.
البته کتاب پارسه این زبانو مستقل از متن نمیشناسه.
از نظر من زبان مستقل از متن نیست ولی اگر ممکن هست لطفا بگید از روی چه منبعی دارید این رو میگید
چون من تو کتاب لینز که نگاه کردم همچین بخشی وجود نداشت اگر ممکنه عکس اون قسمت یا لینکی ازش بگذارید تا بیشتر روش فکر کنیم
کتاب مرجع لینز، تمرینهای منتخبو انتهاش حل کرده.
این لینک ویرایش سومه که این تمرین رو داره
البه تو ترجمه آقای صراف زاده هم هست.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
متن زبان اصلیشو ضمیمه کردم:
مستقل از متن هست تو کتاب سیپسر گفته می تونید ببینید.
دوستان اگه بخوان من میتونم ماشین پشته ای این زبان رو براتون بکشم.
مستقل از متن است و npda هست
چون ما هی پوش میکنیم تا یه ۱ i دلخواه حدس می زنیم که برابر نیست.همین
سلام. گرامرش میشه:
[tex]S\to PL|RP|AD|BC|DA|CB[/tex]
[tex]L\to PLP|PL|c[/tex]
[tex]R\to PRP|RP|c[/tex]
[tex]A\to PAP|a[/tex]
[tex]B\to PBP|b[/tex]
[tex]C\to PCP|cA|Ac[/tex]
[tex]D\to PDP|cB|Bc[/tex]
[tex]P\to a|b[/tex]
[tex]L\to PLP|PL|c[/tex]
[tex]R\to PRP|RP|c[/tex]
[tex]A\to PAP|a[/tex]
[tex]B\to PBP|b[/tex]
[tex]C\to PCP|cA|Ac[/tex]
[tex]D\to PDP|cB|Bc[/tex]
[tex]P\to a|b[/tex]
حتما مستقل از متن هست w1 در پشته push میشود به ازا a میتوان A و به ازا b میتوان B را وارد پشته کرد بعه رسیدن به عنصر جداکننده c آنگاه عمل pop شروع میشه و اگه w2 عناصرش با رشته w1 یکسان نبود به حالت پایانی میرویم لذا حتما مستقل از متن هستش
آقا یاسر رشته به فرم W1cW2 هست که W1 و W2 نباید مثل هم باشن. رشته دوم ریورس نیست. این ماشین نامعینه که باید بگیم یا طول این دو زیررشته برابر نیست و یا حداقل توی یه حرف اختلاف دارن.
(۲۲ خرداد ۱۳۹۱ ۰۱:۱۰ ق.ظ)Jooybari نوشته شده توسط: آقا یاسر رشته به فرم W1cW2 هست که W1 و W2 نباید مثل هم باشن. رشته دوم ریورس نیست. این ماشین نامعینه که باید بگیم یا طول این دو زیررشته برابر نیست و یا حداقل توی یه حرف اختلاف دارن.اره منم حرفت رو تایید میکنم منظور منم همین بود اره نامعینه
این چیزی که من توی پاسختون میبینم به نظرم صورت سوال رو درست نخوندین. پوش کردن ما فقط بخاطر پیداکردن مکان یک حرفه. توی پشته چه بجای a و چه b میتونیم ۱ پوش کنیم. بعدش فقط به یه حرف خاص توجه میکنیم. توضیح شما برای وقتیه که بجای پشته از صف استفاده کنیم. چون ما معکوس رشته رو که نمیخاهیم چک کنیم. خود رشته رو چک میکنیم.
(۲۲ خرداد ۱۳۹۱ ۰۱:۴۲ ق.ظ)Jooybari نوشته شده توسط: این چیزی که من توی پاسختون میبینم به نظرم صورت سوال رو درست نخوندین. پوش کردن ما فقط بخاطر پیداکردن مکان یک حرفه. توی پشته چه بجای a و چه b میتونیم ۱ پوش کنیم. بعدش فقط به یه حرف خاص توجه میکنیم. توضیح شما برای وقتیه که بجای پشته از صف استفاده کنیم. چون ما معکوس رشته رو که نمیخاهیم چک کنیم. خود رشته رو چک میکنیم.کتاب سودکمپ رو خوندی ؟ مثل حل این سوالات رو مثال داده بنده مثل اون عمل کردم و گفتم .
اما حرف شما درسته حل من میشه همون reverse .
حالا شرکتم شیفت شب برسم خونه حل کامل رو که مدنظرمه قرار میدم
(۱۱ دى ۱۳۹۰ ۰۶:۲۳ ب.ظ)reyhaneh64 نوشته شده توسط: آیا زبان زیر مستقل از متن است؟دوستان من این درس رو با استاد ریاحی داشتم از خودشون پرسیدم گفت من کتاب حل تمرین رو موقعی که دانشجوی لیسانس بودم نوشتم و اینکه دیگه ویرایش نکردم ایشون هم گفتن این زبان مستقل از متن هست. و حل تمرین ایشون بعضی جاهاش کمو بیش اشکال دیده میشه و نظر خودشون هم هست که اشکال داره.
[tex]L= w_{1}cw_{2}}: w_{1},w_{2}\epsilon \begin{Bmatrix}a,b \end{Bmatrix}^{*},w1 \neq w2[/tex]
انتهای کتاب جواب داده که هست( لازم به ذکره که حل تمرین ناقوس خلاف اینو گفته!!!)