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

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

ارسال:
  

reyhaneh64 پرسیده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

آیا زبان زیر مستقل از متن است؟
[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 را انتخاب میکند.


مفهوم این توضیحاتو برای پیاده سازی روی ماشین متوجه نمیشم و نمیدونم چطور پیادش کنم
ممنون میشم یاری کنید.

۰
ارسال:
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

سلام. گرامرش میشه:

[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]

۰
ارسال:
  

a_azarbarzin پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

ارسال:
  

reyhaneh64 پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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


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

۰
ارسال:
  

lsamimi پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

۰
ارسال:
  

reyhaneh64 پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

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

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


فایل‌(های) پیوست شده

۰
ارسال:
  

nmusavi پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

۰
ارسال:
  

nmusavi پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

۰
ارسال:
  

vampire2 پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

۰
ارسال: #۱۰
  

yaser_ilam_com پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

۰
ارسال: #۱۱
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

ارسال: #۱۲
  

yaser_ilam_com پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

۰
ارسال: #۱۳
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

ارسال: #۱۴
  

yaser_ilam_com پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

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

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

۰
ارسال: #۱۵
  

nmusavi پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

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

۰
ارسال: #۱۶
  

arash1366 پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

۰
ارسال: #۱۷
  

javadem پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

از اونجایی که ماشین پشته ای توانایی محاسبه برابری w1 با w2 را ندارد. پس نمیتواند عدم برابری آنها را نیز محاسبه کند. پس این عدم توانایی ماشین پشته ای عدم مستقل از متن بودن را تایید میکند.

۰
ارسال: #۱۸
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

ارسال: #۱۹
  

javadem پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

(۰۸ مرداد ۱۳۹۱ ۰۴:۱۶ ب.ظ)Jooybari نوشته شده توسط:  سلام. عدم برابری با برابر فرق میکنه. برای تشخیص عدم برابری اختلاف یک حرف کافیه. فقط کافیه یک حرف رو چک کنیم.

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

۰
ارسال: #۲۰
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

دوست عزیز گرامرشو در
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نوشته بودم. یک رشته بگید که جزء جواب باشه و این گرامر تولید نکنه و یا یک رشته بگید که گرامر تولید میکنه و جزء زبان نیست.
این اطمینان رو منم تا ۱۰ دقیقه قبل از امتحان پایانترم نظریه داشتم. سوال ۱ نظریه ما بود ثابت کنید این رشته مستقل از متن است. قبول دارم توضیحش خیلی سخته. ولی میشه یه dpda براش کشید.
توی pda این ماشین ما به کل رشته کاری نداریم. فقط یک حرف رو در حافظه محدودمون نگه میداریم و مکان اون حرف رو با پشته مشخص میکنیم. اگه بعد از c در همون مکان حرف مخالف حرف ذخیره شده بود به حالت پایانی میریم. چون نامعینه تمام حروف قبل از c رو چک میکنه. یک حالت هم میشه برای برابر نبودن طولها درنظر گرفت.

۰
ارسال: #۲۱
  

javadem پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

ببخشید شما از کجا میدونید کدوم حرف قراره متفاوت باشه که اونو تو حافظه موقت نگه دارید؟
من بعید میدونم، و ندیده مطمئن بودم گرامرت اشتباه است. الانم دیدم که رشته ای که توی زبان نیست رو تولید میکنه یعنی
S-->AD-->PAPD-->aAPD-->aaPD-->aaaD-->aaacB-->aaacPAP-->aaacaAP-->aaacaaP-->aaacaaa
که aaacaaa در زبان نیست.
اگر هم میگید که B میرود به PBP اونوقت من میخوام با این گرامر ، این رشته رو تولید کنم که نمیشه. bbbcbba
این رشته درون زبان هست اما گرامر شما نمیپذیردش.
من بی شک میگم که اشتباه میکنید.
گرامر خوبی بود.اما متاسفانه یه ایراد کوچیک داشت.

۰
ارسال: #۲۲
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

ببخشید مثل اینکه یه اشکال توی گرامر بود که رفع شد. باید مینوشتم 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
این رشته رو قبول میکنه. حتی با گرامر غلط هم پذیرفته بود.

۰
ارسال: #۲۳
  

javadem پاسخ داده:

RE: بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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

اگر مقدار اولیه پشته 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 کنم. مجبور شدم خودشو گذاشتم.

۰
ارسال: #۲۴
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

راستش اولین بار بود که گرامرشو نوشتم. قبلاً ماشینشو کشیده بودم که خیلی بزرگ شده بود. این گرامر رو از روی گرامر w1w2 که دو رشته اندازشون برابره و خودشون برابر نیستن نوشتم. فرقش با این زبان اینه که c نداره.
گرامر اون راحت تر بود. گرامرم اینجوری کار میکنه:
PR و LP برای تولید رشته هاییه که طول دو طرف حرف c برابر نیست. بقیشم دقیقاً مشابه همون w1w2 کار میکنه ولی در یکی از فضاهای بین حروف، حرف c رو قرار میده.

۰
ارسال: #۲۵
  

javadem پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

گرامر خوبی بود فقط یه جا ضعف داشت. اونم اینکه طول رشته ها برابر باشه اول و اخر دو تا هم با هم برابر باشه قبول نمیکنه.
چون فقط طول رشته و اول و آخر رشته رو چک میکنه.
امیدوارم که موفق باشید.

۰
ارسال: #۲۶
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

حرف شما رو قبول ندارم. چندتا رشته بگید که فکر میکنید گرامر قبول نمیکنه ولی جزء زبانه.

۰
ارسال: #۲۷
  

javadem پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

بله من اشتباه کردم. کامل توجه نکردم. درسته گرامر کاملا درسته.
نمیدونم چرا اینقدر رو این گرامر به اشتباه افتادم. کم توجهی کردم ببخشید.

۰
ارسال: #۲۸
  

Jooybari پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

برای این رشته:
S->AD->PAPD->babD->babPDP->babbDb->babbPDPb->babbaDab->babbaPDPab->babbabDbab->babbabcBbab->babbabcPBPbab->babbabcbbbbab
کافیه اون حرفی که اختلاف داره رو هسته درنظر بگیریم.

۰
ارسال: #۲۹
  

javadem پاسخ داده:

بخش ۱-۸، سوال ۱۰(مستقل از متن هست یا نه)

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  چرا مستقل از متنه؟ Wa^nb^mW^R poldasht ۱۱ ۲,۷۸۶ ۱۴ بهمن ۱۳۹۳ ۰۹:۱۰ ب.ظ
آخرین ارسال: ss.hoseini
  خواص مستقل از متن maryam.roshan ۳ ۱,۸۵۵ ۱۲ بهمن ۱۳۹۳ ۱۱:۰۱ ب.ظ
آخرین ارسال: fatemeh69
  تشخیص قطعی بودن ۴ زبان مستقل از متن MR.oracle ۹ ۳,۰۹۳ ۱۲ بهمن ۱۳۹۳ ۱۲:۲۳ ب.ظ
آخرین ارسال: ریحان
  چرا عکس نقیض لم تزریق مستقل از متن نشان دهنده نامنظم بودنه؟ ریحان ۷ ۱,۸۸۷ ۱۲ بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ
آخرین ارسال: ریحان
Question تشخیص زبان های مستقل از متن Ametrine ۹ ۳,۴۷۶ ۱۲ بهمن ۱۳۹۳ ۰۱:۵۱ ق.ظ
آخرین ارسال: ریحان
  چرا n(a)=!n(b) مستقل از متن قطعیه؟ ریحان ۸ ۲,۰۵۰ ۱۱ بهمن ۱۳۹۳ ۱۱:۰۲ ب.ظ
آخرین ارسال: ریحان
  آیا این زبان مستقل از متن است؟؟ K<=max(i,j) Imankhani ۸ ۲,۴۲۱ ۱۱ بهمن ۱۳۹۳ ۰۷:۴۷ ب.ظ
آخرین ارسال: ریحان
  تشخیص اجتماع و اشتراک یک زبان جساس به متن با مستقل از متن یا منظم maryam.roshan ۱ ۱,۲۷۸ ۱۱ بهمن ۱۳۹۳ ۱۲:۴۳ ق.ظ
آخرین ارسال: fatemeh69
  آیا مستقل از متن قطعی است؟${a^mb^mc^n:0≤m≤n≤۲m\}$ archer22 ۳ ۱,۵۶۹ ۰۷ بهمن ۱۳۹۳ ۰۹:۰۲ ب.ظ
آخرین ارسال: Hamid_0311
  مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی mostafa2012 ۴ ۱,۹۱۳ ۰۶ بهمن ۱۳۹۳ ۰۲:۳۲ ب.ظ
آخرین ارسال: mostafa2012

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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