19 دى 1391, 12:29 ب.ظ
19 دى 1391, 01:56 ب.ظ
به نظرم آره مستقل از متنه.ماشین پشته ای رو طوری میسازیم که اگه به این وضعیت رسید پذیرفته نشه(حالت پایانی نباشه).و حالات دیگه رو هم حالات پذیرفته شدنی در نظر میگیریم
19 دى 1391, 03:15 ب.ظ
سلام. بله مستقل از متن هست.
w = w^r
S ----> aSa | bSb | landa
-------------------------------
w <> w^r
S ----> aSb | bSa | landa
پس هر دوی این زبان ها مستقل از متن هستند.
w = w^r
S ----> aSa | bSb | landa
-------------------------------
w <> w^r
S ----> aSb | bSa | landa
پس هر دوی این زبان ها مستقل از متن هستند.
19 دى 1391, 03:51 ب.ظ
سلام. اول یه توضیحی درمورد سوال بدم. بهتر بود صورت سوال بصورت [tex]L=\{w_1w_2|w_1\neq {w_2}^R,|w_1|=|w_2|\}[/tex] چون اگه شرط برابری اندازه نداشته باشن زبانمون میشه سیکماپلاس.
برای نامساوی بودن کافیه یه حرفشون یکی نباشه:
[tex]S\to aSa|bSb|A[/tex]
[tex]A\to aBb|bBa[/tex]
[tex]B\to aBa|aBb|bBa|bBb|\lambda[/tex]
ماشینی که برابر بودن رو بررسی میکنه نامعینه! نمیتونیم بگیم حالتی که برای اون پایانی باشه رو برای این پایانی نگیریم. برای طراحی ماشینش یه جایی حدس میزنیم که به وسط رسیدیم. بهد از اون تا اونجایی که رشته و پشته یکی بود، پشت سر هم پشته رو خالی میکنیم. اگه یه اختلاف داشت به یه حالت دیگه میریم و فقط چک میکنیم که تعداد حروف باقی مونده ی رشته با حروف داخل پشته برابره یا نه. اگه برابر بودن به حالت پایانی میریم.
برای نامساوی بودن کافیه یه حرفشون یکی نباشه:
[tex]S\to aSa|bSb|A[/tex]
[tex]A\to aBb|bBa[/tex]
[tex]B\to aBa|aBb|bBa|bBb|\lambda[/tex]
(19 دى 1391 01:56 ب.ظ)svk7 نوشته شده توسط: [ -> ]به نظرم آره مستقل از متنه.ماشین پشته ای رو طوری میسازیم که اگه به این وضعیت رسید پذیرفته نشه(حالت پایانی نباشه).و حالات دیگه رو هم حالات پذیرفته شدنی در نظر میگیریم
ماشینی که برابر بودن رو بررسی میکنه نامعینه! نمیتونیم بگیم حالتی که برای اون پایانی باشه رو برای این پایانی نگیریم. برای طراحی ماشینش یه جایی حدس میزنیم که به وسط رسیدیم. بهد از اون تا اونجایی که رشته و پشته یکی بود، پشت سر هم پشته رو خالی میکنیم. اگه یه اختلاف داشت به یه حالت دیگه میریم و فقط چک میکنیم که تعداد حروف باقی مونده ی رشته با حروف داخل پشته برابره یا نه. اگه برابر بودن به حالت پایانی میریم.
19 دى 1391, 05:32 ب.ظ
(19 دى 1391 03:51 ب.ظ)Jooybari نوشته شده توسط: [ -> ]ماشینی که برابر بودن رو بررسی میکنه نامعینه!اینو اگه میشه یکم بیشتر توضیح بده
19 دى 1391, 06:23 ب.ظ
(19 دى 1391 05:32 ب.ظ)svk7 نوشته شده توسط: [ -> ](19 دى 1391 03:51 ب.ظ)Jooybari نوشته شده توسط: [ -> ]ماشینی که برابر بودن رو بررسی میکنه نامعینه!اینو اگه میشه یکم بیشتر توضیح بده
ما دقیقاً نمیدونیم کی به وسط رشته میرسیم. وسط رشته رو حدس میزنیم. ماشین بدبخت هم باید تمام حالات رو بررسی کنه و اگه یکیشون جواب داد، بگه رشته پذیرفتست. مثلا برای رشته abbaabba ماشین از کجا میدونه که تا کی باید حروف رو داخل پشته پوش کنه، کی به وسط رشته رسیده و بعد مقایسه رو انجام بده. یکبار w1 رو نال میگیره؛ به جواب نمیرسه. دفعه بعد w=a رو درنظر میگیره و بازم به جواب نمیرسه. در نهایت با w=abba به جواب میرسه و رشته رو قبول میکنه. اگه برای مثال زبان a^nb^n بود مرز بین a و b مشخص بود و ماشین معین میشد. یا اگه مثلاً بین w1 و w2 یه حرف مثل c بود اونموقع هم معلوم بود.
20 دى 1391, 09:59 ق.ظ
(19 دى 1391 03:51 ب.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. اول یه توضیحی درمورد سوال بدم. بهتر بود صورت سوال بصورت [tex]L=\{w_1w_2|w_1\neq {w_2}^R,|w_1|=|w_2|\}[/tex] چون اگه شرط برابری اندازه نداشته باشن زبانمون میشه سیکمااستار.سلام
برای نامساوی بودن کافیه یه حرفشون یکی نباشه:
[tex]S\to aSa|bSb|A[/tex]
[tex]A\to aBb|bBa[/tex]
[tex]B\to aBa|aBb|bBa|bBb|\lambda[/tex]
اگه w1 و w2 عضو سیگما استار باشن، نمیشه، w2 رو رشته ای به طول صفر در نظر گرفت، بگیم زبان منظم هست؟
در صورتیکه w1,w2 عضو سیگما پلاس باشن، مستقل از متن میشه
20 دى 1391, 11:36 ق.ظ
(19 دى 1391 03:15 ب.ظ)azad_ahmadi نوشته شده توسط: [ -> ]سلام. بله مستقل از متن هست.
w = w^r
S ----> aSa | bSb | landa
-------------------------------
w <> w^r
S ----> aSb | bSa | landa
پس هر دوی این زبان ها مستقل از متن هستند.
فکر می کردم که سوال WW^R | {a,b} ozv sigma star هست.
20 دى 1391, 08:24 ب.ظ
(20 دى 1391 09:59 ق.ظ)Shiny_Star نوشته شده توسط: [ -> ]سلام
اگه w1 و w2 عضو سیگما استار باشن، نمیشه، w2 رو رشته ای به طول صفر در نظر گرفت، بگیم زبان منظم هست؟
در صورتیکه w1,w2 عضو سیگما پلاس باشن، مستقل از متن میشه
فرض من از سوال برابر بودن طول دو رشتست. اگه قرار باشه طولشون برابر نباشه، چه عضو سیکمااستار و چه سیکماپلاس که باشن منظمه.