۰
subtitle
ارسال: #۱
زبان مستقل از متنW=!W^R
سلام.
میدانیم که (w = w^R) مستقل از متن هست.
اما آیا (w <> w^R) هم مستقل از متن هست ؟؟؟
w^R یعنی معکوس عبارت w .
<> یعنی نامساوی.
میدانیم که (w = w^R) مستقل از متن هست.
اما آیا (w <> w^R) هم مستقل از متن هست ؟؟؟
w^R یعنی معکوس عبارت w .
<> یعنی نامساوی.
۰
ارسال: #۲
زبان مستقل از متن؟
سلام. اول یه توضیحی درمورد سوال بدم. بهتر بود صورت سوال بصورت [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]
(۱۹ دى ۱۳۹۱ ۰۱:۵۶ ب.ظ)svk7 نوشته شده توسط: به نظرم آره مستقل از متنه.ماشین پشته ای رو طوری میسازیم که اگه به این وضعیت رسید پذیرفته نشه(حالت پایانی نباشه).و حالات دیگه رو هم حالات پذیرفته شدنی در نظر میگیریم
ماشینی که برابر بودن رو بررسی میکنه نامعینه! نمیتونیم بگیم حالتی که برای اون پایانی باشه رو برای این پایانی نگیریم. برای طراحی ماشینش یه جایی حدس میزنیم که به وسط رسیدیم. بهد از اون تا اونجایی که رشته و پشته یکی بود، پشت سر هم پشته رو خالی میکنیم. اگه یه اختلاف داشت به یه حالت دیگه میریم و فقط چک میکنیم که تعداد حروف باقی مونده ی رشته با حروف داخل پشته برابره یا نه. اگه برابر بودن به حالت پایانی میریم.
ارسال: #۳
RE: زبان مستقل از متن؟
(۱۹ دى ۱۳۹۱ ۰۳:۵۱ ب.ظ)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 عضو سیگما پلاس باشن، مستقل از متن میشه
۰
ارسال: #۴
RE: زبان مستقل از متن؟
به نظرم آره مستقل از متنه.ماشین پشته ای رو طوری میسازیم که اگه به این وضعیت رسید پذیرفته نشه(حالت پایانی نباشه).و حالات دیگه رو هم حالات پذیرفته شدنی در نظر میگیریم
۰
ارسال: #۵
زبان مستقل از متن؟
سلام. بله مستقل از متن هست.
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
پس هر دوی این زبان ها مستقل از متن هستند.
ارسال: #۶
RE: زبان مستقل از متن؟
۰
ارسال: #۷
زبان مستقل از متن؟
ارسال: #۸
RE: زبان مستقل از متن؟
(۱۹ دى ۱۳۹۱ ۰۵:۳۲ ب.ظ)svk7 نوشته شده توسط:(19 دى ۱۳۹۱ ۰۳:۵۱ ب.ظ)Jooybari نوشته شده توسط: ماشینی که برابر بودن رو بررسی میکنه نامعینه!اینو اگه میشه یکم بیشتر توضیح بده
ما دقیقاً نمیدونیم کی به وسط رشته میرسیم. وسط رشته رو حدس میزنیم. ماشین بدبخت هم باید تمام حالات رو بررسی کنه و اگه یکیشون جواب داد، بگه رشته پذیرفتست. مثلا برای رشته abbaabba ماشین از کجا میدونه که تا کی باید حروف رو داخل پشته پوش کنه، کی به وسط رشته رسیده و بعد مقایسه رو انجام بده. یکبار w1 رو نال میگیره؛ به جواب نمیرسه. دفعه بعد w=a رو درنظر میگیره و بازم به جواب نمیرسه. در نهایت با w=abba به جواب میرسه و رشته رو قبول میکنه. اگه برای مثال زبان a^nb^n بود مرز بین a و b مشخص بود و ماشین معین میشد. یا اگه مثلاً بین w1 و w2 یه حرف مثل c بود اونموقع هم معلوم بود.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close