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

نحوه‌ی ساخت 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



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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