سلام دوستان خسته نباشید
_ ارشد پارسال که دادم، سنجش زبان "An B2n An" را غیر مستقل ازمتن اعلام کرده! (A,B عضو الفبا. n توان)
مگه این رشته عضو w wR نیست؟!! به نظر من چون نیاز به دانستن وسط رشته هم میباشد، مستقل ازمتن غیرقطعی میباشد!
ممنون میشم کمکی بکنید
سلام
این روش اصلا برای تشخیص مستقل از متن بودن درست نیست
اگه این روش شما درست باشه شما می تونی بگی زبان [tex]a^nb^{2n}a^n[/tex] زیر مجموعه ی سیگما استاره پس منظمه
اصلا هر زبانی زیر مجموعه ی سیگما استاره پس هر زبانی منظمه
خب پس این استدلال غلطه که بخواهید بگید چون زیر مجموعه ی [tex]ww^R[/tex] است پس مستقل از متنه
استدلالش اینجوزیه که ما هر چی a می بیینم به ازای هر a یه نماد داخل پشته می ذاریم وقتی a ها تموم بشه ما n تا a داخل پشته داریم به b ها که رسیدیم به ازای هر دوتا b یه دونه نماد از پشته بر می داریم وقتی b ها تموم شد دیگه پشته خالی شده و ما دیگه n رو نداریم که بخواهیم بدونیم آیا تعداد a ها ی آخر رشته برابر n تاست یا نه.
پس این زبان رو نمی شه با پشته پذیرش کرد چون از تعداد n سه بار استفاده کرد به عبارتی دوبار مقایسه با یه عامل داره. یه بار مقایسه بین A ها ی اول و b هاست یه بار مقایسه بین b ها و a های آخر که می بینید که تو این دو مقایسه عامل "تعداد b ها" مشترکه و پشته نمی تونه در یک مسیر محاسبه دو مقایسه با عامل مشترک انجام بده
خب یعنی مستقل از متن نیست؟
(11 بهمن 1393 07:56 ب.ظ)ریحان نوشته شده توسط: [ -> ]خب یعنی مستقل از متن نیست؟
نع، ببین پشته سه تا یکسان رو نمتونه با هم مقایسه کنه
درسته
میشه بگید زبان W1 C W2 چرا مستقل ازمتنه؟؟
عایا چون C داره زبان اولی کاری به دومی نداره و نیازی به مچ و این رفا نیست؟ به همین راحتی؟
و زبان W C W چرا مستقل از متن نیست؟عایا چون نمیتونیم با استک رشته های W قبل C را با رشته های بعد C مچ کنیم و دسترسی بهم ندارن ؟
وزبان WW که W مخالف W^R چرا مستقل از متن قطعیه؟
اینو دیگه توجیهی ندارم....
راستی مگه اگه W=W^R باشه قطعیه؟ که مکملش که بالاییه هم مستقل از متن قطعی شه؟ اخه C نداره وسطش که...چطوری قطعیه؟
میدونیمم قطعیا تحت مکمل بسته اند...
جبل عاملی گفته مستقل از متن قطعی و منظم(همه منظمها مستقل از متن قطعی اند) تحت اجتماع و اشتراک و تفاضل بسته هستند
اشتباه که نگفته؟ انگاری لینز گفته بسته نیستن......Confused
بسیار ممنون ازلطفتون
پس یعنی شما میگید wwRبرای هر wصحیح نیست؟؟!!! نمیدونم، من که گیج شدم
_استدلال من اینطوری بود: برای رشته wwR؛ چگونه w را با wR جدا میکردیم؟؟ فرض ما این بود وسط رشته را میدونیم (مستقل از متن غیرقطعی)! پس برایه این رشته وقتی به a رسیدیم تو پشته a میگذاریم، به b که رسیدیم، a خط میزنیم "اگر به وسط رشته رسیدیم و پشته خالی" ادامه میدهیم؛ سپس دوباره همین کارا برای ادامه رشته انجام میدیم! (امیدوارم منظورما رسونده باشم)
با این استدلال an bn cn dn هم مستقل از متن هست!! نمیدونم کجایه استدلالم اشتباست؟؟
خیلی ممنون از وقتی که میذارید
اما ببخشید من منظورتونا نفهمیدم! بحث اصلی منم همین an b2n an! کنکور سال قبل گفته این زبان مستقل ازمتن نیست، اما من با استدلالی که گفتم مستقل از متن میدونم
(15 بهمن 1393 01:09 ب.ظ)sepehr . kh نوشته شده توسط: [ -> ]خیلی ممنون از وقتی که میذارید
اما ببخشید من منظورتونا نفهمیدم! بحث اصلی منم همین an b2n an! کنکور سال قبل گفته این زبان مستقل ازمتن نیست، اما من با استدلالی که گفتم مستقل از متن میدونم
خب اشتباه شما تو اون pda ای که نوشتید این بود که وقتی یه بار a ها را داخل پشته می ریزید و با b ها پاپ می کنید تا این جا تضمین می کنید که قسمت[tex]a^nb^n[/tex] از ورودی رو دیده باشید
بعد که بقیه ی b ها رو داخل پشته می ریزید و با a ها پاپ می کنید تضمین می کنید که ادامه ی b ها با بخش آخر a ها تعداد مساوی داشته باشند یعنی تضمن می کنید که از این جا به بعد [tex]a^mb^m[/tex]ببنید
و در کل شما رشته ی [tex]a^nb^na^mb^m[/tex] می پذیرید و تضمینی برای این که m با n برابر باشد در pda شما وچود ندارد
عذر می خوام جواب قبلی م کلا غلط بود پاکش کردم
کدوم غلط یووووووود؟
(15 بهمن 1393 06:00 ب.ظ)ریحان نوشته شده توسط: [ -> ]کدوم غلط یووووووود؟
همونی که گفته بودم این زبان قطعیه!!!!!!