سلام
این زبان رو ببینید، من توی جزوه ام نوشتم که این مستقل از متن هست ولی اگر بجای نامساوی، مساوری بود دیگه مستقل از متن نمیشد:
![[تصویر: 229845_automata-problem.jpg]](https://img.manesht.ir/229845_automata-problem.jpg)
ولی توی یه جای دیگه دیدم که نوشته بود این مستقل از متن نیست!
نظرتون چیه؟
(۱۸ آذر ۱۳۹۲ ۰۳:۵۷ ب.ظ)هاتف نوشته شده توسط: سلام
این زبان رو ببینید، من توی جزوه ام نوشتم که این مستقل از متن هست ولی اگر بجای نامساوی، مساوری بود دیگه مستقل از متن نمیشد:
ولی توی یه جای دیگه دیدم که نوشته بود این مستقل از متن نیست!
نظرتون چیه؟
سلام آقا هاتف
به نظر من هم همون چیزی که در جزوتون نوشتید درسته، چون برای اینکه w2 همان w1 را تکرار نکنه نیاز به حافظه داره پس باید مستقل از متن باشه. دوستان هم نظر دهند.
سلام بیاید با هم بررسی کنیم
ابتدا رشته دابلیو ۱ وارد پشته می شه فرضا داریم aabbabcbba حالا به c رسیدیم و در ابتدای رشته دابلیو ۲ می خوایم اولین حرف رشته ی دابلیو ۲ رو با اولین حرف رشته دابلیو ۱ تطبیق بدیماما در پشته ما حرف اول رشته دابلیو ۱ رو نداریم یعنی ما به a دست رسی نداریم بلکه بالای پشته حرف اخر رشته دابلیو ۱ یا همون b ذخیره شده
همون طور کی می دونید وقتی ما از پشته استفاه می کنیم FILO هست یعنی اونی که اول وارد کردی اخریه که خارج می شه
به عبارتی با ماشین پشته ای قابل به توصیف این زبان ها نیستیم یعنی مستقل از متن نیستن هیچ کدومشون
حالا فرض کنیم که داشتیم W1cW2R در چنین زبانی چطور؟
می بینید که دیگه این نقص وجود نداره چون در ریرس یک رشته ما داریم اخرین حرف از رشته دابلیو ۱ رو با اولین حرف از رشته دابلیو ۲ تطبیق می دیم
موفق باشید
سلام. این سوال از مجموعه سوالتیه که همیشه درموردشون بحث بوده. دو زبان زیر رو درنظر بگیرید:
[tex]L_1=\{W_1cW_2|W_1,W_2\in \{a,b\}^*,W_1\neq W_2\}[/tex]
[tex]L_2=\{W_1W_2|W_1,W_2\in \{a,b\}^*,|W_1|=|W_2|,W_1\neq W_2\}[/tex]
هردو زبان فوق مستقل از متن غیر قطعی هستن. چندین بار هم در انجمن درموردشون بحث شده. در هر مقایسه تو ماشین پشته ای فقط دو حرف در یک مکان مشخص مقایسه میشن و اگه یکی نبودن به حالت پایانی میریم.
دو زبان زیر رو هم درنظر بگیرید:
[tex]L_3=\{W_1cW_2|W_1,W_2\in \{a,b\}^*,W_1= W_2\}[/tex]
[tex]L_4=\{W_1W_2|W_1,W_2\in \{a,b\}^*,|W_1|=|W_2|,W_1= W_2\}[/tex]
هیچکدوم مستقل از متن نیستن.
موفق باشید.
(۲۰ آذر ۱۳۹۲ ۰۴:۱۷ ب.ظ)Jooybari نوشته شده توسط: [tex]L_1=\{W_1cW_2|W_1,W_2\in \{a,b\}^*,W_1\neq W_2\}[/tex]
[tex]L_2=\{W_1W_2|W_1,W_2\in \{a,b\}^*,|W_1|=|W_2|,W_1\neq W_2\}[/tex]
هردو زبان فوق مستقل از متن غیر قطعی هستن.
چطور به عنصر اول w1 که اکنون در ته پشته است برای مقایسه کردن با عنصر اول w2که اکنون در سر پشته است دسترسی پیدا میکنید
(۲۱ آذر ۱۳۹۲ ۰۳:۰۰ ق.ظ)atharrashno نوشته شده توسط: چطور به عنصر اول w1 که اکنون در ته پشته است برای مقایسه کردن با عنصر اول w2که اکنون در سر پشته است دسترسی پیدا میکنید
قرار نیست کل رشته رو بفرستیم به پشته. در هر مرحله فقط یه حرف رو چک میکنیم. اگه برابر نبودن به مرحله نهایی میره همین. یه الگوریتم خلاصه و سریع (شماره خط همون شماره حالته.):
۱- اگه a یا b دیدی به پشته ۱ اضافه کن. اگه a دیدی به ۲ برو. اگه b دیدی به ۳ برو.
۲- تا زمانی که a یا b دیدی رشته رو بخون. اگه c دیدی به ۴ برو.
۳- تا زمانی که a یا b دیدی رشته رو بخون. اگه c دیدی به ۵ برو.
۴- تا زمانی که به انتهای رشته نرسیدی یک حرف از ورودی بخون. اگه به انتهای پشته رسیدی و حرف رشته a بود به تله برو و در غیر این صورت به حالت پایانی برو.
۵- تا زمانی که به انتهای رشته نرسیدی یک حرف از ورودی بخون. اگه به انتهای پشته رسیدی و حرف رشته b بود به تله برو و در غیر این صورت به حالت پایانی برو.
این سوالات بارها در انجمن مطرح شدن. یه جستجو داشته باشید ضرر نداره.
دوستان پاسخی ک به عنوان پاسخ صحیح مطرح شده غلطه
و با ماهیت پشته و ماشین پشته ای در تناقضه
می تونیم با دو پشته یا با لینک لیست و همین طور با ماشین تورینگ اینو بررسی کنیم ولی با یک پشته نمی شه پس مستقل از متن نیستن
پیشنهاد می کنم سعی کنید مطابق توضیحاتی ک در ادامه برای دسترسی به حروف دادن ماشینش رو رسم کنید و بعد رشته ای رو روی ماشین پیاده کنید
البته من اصلا دوست ندارم بحث کنم ولی احساس مسیولیت کردم ک برای اخرین بار هم این مساله رو عنوان کنم
امیدوارم ازرده نشن دوستمون
:
قرار نیست کل رشته رو بفرستیم به پشته. در هر مرحله فقط یه حرف رو چک میکنیم. اگه برابر نبودن به مرحله نهایی میره همین. یه الگوریتم خلاصه و سریع (شماره خط همون شماره حالته.):
۱- اگه a یا b دیدی به پشته ۱ اضافه کن. اگه a دیدی به ۲ برو. اگه b دیدی به ۳ برو.
۲- تا زمانی که a یا b دیدی رشته رو بخون. اگه c دیدی به ۴ برو.
۳- تا زمانی که a یا b دیدی رشته رو بخون. اگه c دیدی به ۵ برو.
۴- تا زمانی که به انتهای رشته نرسیدی یک حرف از ورودی بخون. اگه به انتهای پشته رسیدی و حرف رشته a بود به تله برو و در غیر این صورت به حالت پایانی برو.
۵- تا زمانی که به انتهای رشته نرسیدی یک حرف از ورودی بخون. اگه به انتهای پشته رسیدی و حرف رشته b بود به تله برو و در غیر این صورت به حالت پایانی برو.
این سوالات بارها در انجمن مطرح شدن. یه جستجو داشته باشید ضرر نداره.
الان شما داری فقط حرف اول رو از رشته ی ۱ ذخیره می کنی
بعدش هم اخرین حرف رو از رشته ی ۲ با این اولین حرف از رشته ی مقایسه می کنی
یعنی در واقع ماشین شما هیچ ربطی به مورد سوال نداره
اینی ک شما می گی مال ماشین تورینگه که یم تونیم برگردیم از ابتدای رشته ولی در ماشین پشته ای ما فقط یک بار هر حرف رو می خونیم یعنی نیم شه دفعه اول ک کل رشته رو می خونی یک حرف رو بررسی کنی و دفعه دوم حرف بعدی و ... کلا ما در ماشین پشته ای و در اتوماتا ها به طور کلی کلا یک بار کل رشته رو مرور می کنیم
پس کلا ماشین پیشنهادی شما غلطه
آقای جویباری منظور شما اینه که اگه من این رشته رو داشته باشم برای زبان L1: abacbba
خب من اول a میذارم داخل پشته و به مرحله ۴ میرم وبه آخر رشته میرسم و باز a میبینم پس به حالت تله میرم در حالی که رشته های من مخالف هم هستن.
حالا باز بیام واسه کاراکتر دوم اینکارو انجام بدم؟!
اگر مدیران فروم لینک بحث شده این سوال را دارند خواهشمندیم لینک بزارند در جست و جوهای سوالات اعضا حل مساله و جستجوی خود تالار با کلمه مستقل از متن لینک مذکور یافت نشد
(۱۸ آذر ۱۳۹۲ ۰۴:۱۱ ب.ظ)misagh01 نوشته شده توسط:(18 آذر ۱۳۹۲ ۰۳:۵۷ ب.ظ)هاتف نوشته شده توسط: سلام
این زبان رو ببینید، من توی جزوه ام نوشتم که این مستقل از متن هست ولی اگر بجای نامساوی، مساوری بود دیگه مستقل از متن نمیشد:
ولی توی یه جای دیگه دیدم که نوشته بود این مستقل از متن نیست!
نظرتون چیه؟
سلام آقا هاتف
به نظر من هم همون چیزی که در جزوتون نوشتید درسته، چون برای اینکه w2 همان w1 را تکرار نکنه نیاز به حافظه داره پس باید مستقل از متن باشه. دوستان هم نظر دهند.
ماشین پشته ای این زبان رو برام می کشید؟
ماشین پشته ای زبان اینکه زبان اول با زبان دوم مخالف هست رو میکشید برام؟
(۲۱ آذر ۱۳۹۲ ۰۲:۴۲ ب.ظ)Jooybari نوشته شده توسط:راه حل شما مشکل داره به نظر من(21 آذر ۱۳۹۲ ۰۳:۰۰ ق.ظ)atharrashno نوشته شده توسط: چطور به عنصر اول w1 که اکنون در ته پشته است برای مقایسه کردن با عنصر اول w2که اکنون در سر پشته است دسترسی پیدا میکنید
قرار نیست کل رشته رو بفرستیم به پشته. در هر مرحله فقط یه حرف رو چک میکنیم. اگه برابر نبودن به مرحله نهایی میره همین. یه الگوریتم خلاصه و سریع (شماره خط همون شماره حالته.):
۱- اگه a یا b دیدی به پشته ۱ اضافه کن. اگه a دیدی به ۲ برو. اگه b دیدی به ۳ برو.
۲- تا زمانی که a یا b دیدی رشته رو بخون. اگه c دیدی به ۴ برو.
۳- تا زمانی که a یا b دیدی رشته رو بخون. اگه c دیدی به ۵ برو.
۴- تا زمانی که به انتهای رشته نرسیدی یک حرف از ورودی بخون. اگه به انتهای پشته رسیدی و حرف رشته a بود به تله برو و در غیر این صورت به حالت پایانی برو.
۵- تا زمانی که به انتهای رشته نرسیدی یک حرف از ورودی بخون. اگه به انتهای پشته رسیدی و حرف رشته b بود به تله برو و در غیر این صورت به حالت پایانی برو.
این سوالات بارها در انجمن مطرح شدن. یه جستجو داشته باشید ضرر نداره.
مثلا برای رشته ی زیر جواب نمی ده
abcab
و به رشته ی پایانی میره
نوشته بودم الگوریتم سریع و خلاصه. باید شرط برابری طول دو طرف c هم چک بشه. در ضمن این رشته به تله میرسه.
(۲۲ آذر ۱۳۹۲ ۰۱:۱۸ ق.ظ)atharrashno نوشته شده توسط: اگر مدیران فروم لینک بحث شده این سوال را دارند خواهشمندیم لینک بزارند در جست و جوهای سوالات اعضا حل مساله و جستجوی خود تالار با کلمه مستقل از متن لینک مذکور یافت نشد
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
به نظرم اینا بودن.
(۲۱ آذر ۱۳۹۲ ۰۹:۲۵ ب.ظ)maryam.raz نوشته شده توسط: آقای جویباری منظور شما اینه که اگه من این رشته رو داشته باشم برای زبان L1: abacbba
خب من اول a میذارم داخل پشته و به مرحله ۴ میرم وبه آخر رشته میرسم و باز a میبینم پس به حالت تله میرم در حالی که رشته های من مخالف هم هستن.
حالا باز بیام واسه کاراکتر دوم اینکارو انجام بدم؟!
ما رشته داخل پشته نمیفرستیم. اندیس یه حرف رو میفرستیم. بعد حرف متناظر رو پیدا میکنیم و مقایسه میکنیم.
(۲۱ آذر ۱۳۹۲ ۰۸:۲۴ ب.ظ)ایزدی نوشته شده توسط: دوستان پاسخی ک به عنوان پاسخ صحیح مطرح شده غلطه
و با ماهیت پشته و ماشین پشته ای در تناقضه
می تونیم با دو پشته یا با لینک لیست و همین طور با ماشین تورینگ اینو بررسی کنیم ولی با یک پشته نمی شه پس مستقل از متن نیستن
پیشنهاد می کنم سعی کنید مطابق توضیحاتی ک در ادامه برای دسترسی به حروف دادن ماشینش رو رسم کنید و بعد رشته ای رو روی ماشین پیاده کنید
البته من اصلا دوست ندارم بحث کنم ولی احساس مسیولیت کردم ک برای اخرین بار هم این مساله رو عنوان کنم
امیدوارم ازرده نشن دوستمون
:
قرار نیست کل رشته رو بفرستیم به پشته. در هر مرحله فقط یه حرف رو چک میکنیم. اگه برابر نبودن به مرحله نهایی میره همین. یه الگوریتم خلاصه و سریع (شماره خط همون شماره حالته.):
۱- اگه a یا b دیدی به پشته ۱ اضافه کن. اگه a دیدی به ۲ برو. اگه b دیدی به ۳ برو.
۲- تا زمانی که a یا b دیدی رشته رو بخون. اگه c دیدی به ۴ برو.
۳- تا زمانی که a یا b دیدی رشته رو بخون. اگه c دیدی به ۵ برو.
۴- تا زمانی که به انتهای رشته نرسیدی یک حرف از ورودی بخون. اگه به انتهای پشته رسیدی و حرف رشته a بود به تله برو و در غیر این صورت به حالت پایانی برو.
۵- تا زمانی که به انتهای رشته نرسیدی یک حرف از ورودی بخون. اگه به انتهای پشته رسیدی و حرف رشته b بود به تله برو و در غیر این صورت به حالت پایانی برو.
این سوالات بارها در انجمن مطرح شدن. یه جستجو داشته باشید ضرر نداره.
الان شما داری فقط حرف اول رو از رشته ی ۱ ذخیره می کنی
بعدش هم اخرین حرف رو از رشته ی ۲ با این اولین حرف از رشته ی مقایسه می کنی
یعنی در واقع ماشین شما هیچ ربطی به مورد سوال نداره
اینی ک شما می گی مال ماشین تورینگه که یم تونیم برگردیم از ابتدای رشته ولی در ماشین پشته ای ما فقط یک بار هر حرف رو می خونیم یعنی نیم شه دفعه اول ک کل رشته رو می خونی یک حرف رو بررسی کنی و دفعه دوم حرف بعدی و ... کلا ما در ماشین پشته ای و در اتوماتا ها به طور کلی کلا یک بار کل رشته رو مرور می کنیم
پس کلا ماشین پیشنهادی شما غلطه
اون چیزی که جلوی ۱ نوشتم ۳ حرکت متفاوته و ربطی به هم ندارن. درواقع:
"اگه a یا b دیدی به پشته ۱ اضافه کن." یه طوقه در حالت ۱ هست.
"اگه a دیدی به ۲ برو." یه یال از ۱ به ۲ هست.
"اگه b دیدی به ۳ برو." یه یال از ۱ به ۳ هست.
این روش هم فقط برای پیدا کردن اختلاف در دو رشتست. برای مقایسه طول دو رشته مقایسه جدا باید داشته باشیم. شما چندتا رشته مثال بزنید تا با همین الگوریتم جواب رو به شما بدم.
من تمرینات قسمت خصوصیات زبانهای مستقل از متن لینز رو نگاه نکرده بودم فکرکردم تمرینات به این صورت نداشته باشه الان دیدم تو لینکهایی که آقای جویباری گذاشته بچه ها گفتن که جز تمرینات لینز بوده!! شد قضیه جواب در کتاب و ما گرد جهان میگردیم
البته لینکی که آقای جویباری گذاشتن هم جوابها رو واضح داده ولی من اینجا مینویسم
برای اینکه ثابت کنیم دو رشته w1,w2 مساوی نیستن بصورت غیرقطعی یک نشانه مثلا kامین رشته رو بخاطر سپرده و با kامین رشته در w2 مقایسه میکنیم اگر برابر نبودند کار تمام است. فقط دقت کنید که گفتیم بصورت غیر قطعی، یعنی پشته ممکنه یه بار عنصر دوم دو رشته رو مقایشه کنه یه بار عنصر مثلا چهارم رو