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

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