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

نحوه‌ی ساخت PDA برای a^nb^m با شرط برابر نبودن توانها

ارسال:
  

mohandeszahra پرسیده:

نحوه‌ی ساخت PDA برای a^nb^m با شرط برابر نبودن توانها

میخوام لطف کنید توضیح بدید این زبان چطور با PDA قابل تشخیصه؟؟
[tex]L={a^{n}b^{m}| n\neq m}[/tex]
[

۰
ارسال:
  

Jooybari پاسخ داده:

نحوه‌ی ساخت PDA?????

سلام. pda این ماشین میتونه به این شکل کار کنه:
در حالت ۱ به ازای هر a که از ورودی دریافت میکنه یه a توی پشته پوش میکنه و در حالت ۱ میمونه (برای راحتی کار به ازای اولین a حرف c پوش میکنیم. یعنی بالای z0 یه c داریم.).
هروقت b دید از حالت ۱ به حالت ۲ میره و یه a پاپ میکنه. اگه روی پشتمون c بود به حالت ۳ میریم.

در حالت ۲ اگه b ورودیمون بود و روی پشته a بود اون a رو از پشته خط میزنیم و در ۲ میمونیم.
در حالت ۲ اگه b ورودیمون بود و روی پشته c بود c رو از پشته خط میزنیم و به ۳ میریم.
در حالت ۲ اگه b ورودیمون بود و روی پشته $ بود همون $ رو اضافه میکنیم و در ۲ میمونیم.
در حالت ۳ اگه b ورودیمون بود با پشته کاری نداریم و به ۲ میریم.( مسلماً روی پشته z0 هست و با خوندن b مقدار m از n بیشتر میشه)
حالت شروع حالت ۱ و حالت پایان حالت ۲ و اگه مقدار m بتونه صفر بشه حالت ۱ هم جزء جوابه.

هرزبان که بشه با PDA پذیرفت میشه برای یه گرامر مستقل از متن نوشت. گرامر این زبان:

S->aSb|A|B
A->aA|a
B->Bb|b



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  شمارا بودن یا نبودن زبانهای R و RE pooyaa ۶ ۲,۰۰۶ ۱۰ بهمن ۱۳۹۳ ۱۱:۲۱ ب.ظ
آخرین ارسال: fatemeh69
  نحوه تشخیص زبان های خطی arefeh.hp ۷ ۲,۷۱۰ ۰۹ بهمن ۱۳۹۳ ۱۲:۰۵ ق.ظ
آخرین ارسال: nazanin2020
  تشخیص نوع گرامر و نحوه ی کار alirezafchh ۱ ۵۲۶ ۱۰ دى ۱۳۹۳ ۰۶:۳۲ ب.ظ
آخرین ارسال: Hamid_0311
  نحوه و روش تقسیم دو زبان s_t_6 ۴ ۴۹۹ ۱۴ مرداد ۱۳۹۳ ۱۱:۴۸ ب.ظ
آخرین ارسال: fatemeh69
Sad سوال فوری و ساده ( مستقل از متن بودن یا نبودن چند زبان ) goldteamasia ۲ ۶۰۶ ۲۵ خرداد ۱۳۹۳ ۰۱:۱۰ ب.ظ
آخرین ارسال: goldteamasia
  برای تست برابر بودن دو زبان مستقل از متن الگوریتمی وجود دارد یا خیر؟ be_sooye_movafaghiat ۱ ۵۱۹ ۰۸ خرداد ۱۳۹۳ ۱۰:۵۵ ق.ظ
آخرین ارسال: Morris
Star بسته بودن یا نبودن زبان های مستقل از متن قطعی تحت استار negar.v ۳ ۶۵۰ ۲۸ اردیبهشت ۱۳۹۳ ۰۴:۲۸ ب.ظ
آخرین ارسال: negar.v
  نحوه پیدا کردن اشتراک دو زبان sonia11 ۸ ۱,۰۶۵ ۱۸ بهمن ۱۳۹۲ ۱۰:۰۳ ب.ظ
آخرین ارسال: sonia11
  زبان های منظم و بسته بودن یا نبودن تحت اشتراک و اجتماع نامتناهی fulgent ۵ ۱,۴۰۸ ۱۶ بهمن ۱۳۹۲ ۰۲:۵۷ ب.ظ
آخرین ارسال: maryam.raz
  وجود گرامر مبهم برای یک DCf و وجود گرامر غیر میهم برای یک NDCF zimenswall ۷ ۱,۴۷۵ ۲۷ آبان ۱۳۹۲ ۰۳:۰۵ ب.ظ
آخرین ارسال: zimenswall

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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