تالار گفتمان مانشت

بچه‌ها دو تا سوال
لطفا هر کس می دونه نظرشو بگه
۱) زبان [tex]a^{2n}b^{n}[/tex] مستقل از متنه درسته؟
یعنی باید در پشته به ازای هرb دو تا b بذاره و با دیدن هر a یک b را pop کنه. درسته؟ حالا اول رشته که همش a است چطوری b‌ها رو pop میکنه؟ کلا چطوری با پشته کار می کنه؟
اصلا چطوری میشه به ازای یه حرف دو تا حرف از روی پشته بر داشت؟ منظورم نوشتن حرکتشه. مثلا برای پاپ کردن یه دونه می گیم:
[tex]\delta (q, a, b)=(q,\lambda )[/tex]
برای دوتا چطور میگیم؟


۲) توی کتاب پیتر لینز صفحه ۲۰۱ گفته زبان های مستقل از متن تحت اجتماع بسته است.
بعد صفحه ۲۰۷ گفته زبان های مستقل از متن غیر گنگ تحت اجتماع بسته نیست.

خب پس مگه اولی گنگا رو می گه؟؟؟؟؟؟

در مورد سوال اول دو نکته درباره‌ی آتاماتای پشته ای غیر قطعی(nPDA) وجود داره اونم اینه که
1) رشته‌ی w در ماشین پذیرفته میشه اگه پس از پیمایش در یک حالت پایانی باشیم و به محتویات پشته کاری نداریم
2)رشته‌ی w در ماشین پذیرفته میشه اگه پس از پیمایش رشته پشته خالی بشه حال چه تو حالت پایانی باشیم و چه نباشیم
پس تو این مثال میشه از نکته‌ی دوم استفاده کرد

خب از این نکته چطور میشه استفاده کرد؟
به سوالات من جواب ندادید. a و b رو چطور توی پشته میذاریم و برمیداریم که آخر پشته خالی می شه؟

1)به دو روش میتونیم عمل کنیم یکی اینکه به ازای هر b دوتا a برداریم یا به ازای هر 2 تا a یکیشو پوش کنیم که این با تغییر وضعیت و استفاده از لاندا امکان پذیره
مثلا در حالت 1 وقتی b دیدیم یه a برداریم و به یه وضعیت جدید بریم توی وضعیت جدید بدون خوندن ورودی یه a دیگه برداریم و به حالت قبل برگردیم
توی حالت 2 هم وقتی a خوندیم پوش کنیم و به وضعیت جدید بریم توی این وضعیت a بخونیم ولی دیگه پوش نکنیم.
و با توجه به اینکه تعداد a‌ها زوجه این کار امکان پذیره.


2) خوب ممکنه دو تا زبان غیر گنگ رو اجتماع کنیم گنگ بشه و احتمالش هم خیلی زیاده که گنگ بشه.
اما اجتماع دو زبان مستقل از متن همیشه مستقل از متنه.

---

مثلا اجتماع این دو زبان مستقل از متن غیر گنگ شده مستقل از متن گنگ

[tex]a^{n}b^{n} \cup a^{2n}b^{n}[/tex]

اول اینکه ببخشید منظورم بودن در حالت پایانی بود که مربوط به نکته‌ی اول میشه
و به این صورت عمل می کنیم که ابتدا در حالت q0 هستیم و بازاء هر a یک A در پشته قرار می دیم و هر وقت b اومد به حالت q1 که حالت پایانی هم هست میریم و به ازاء هر b یک A از پشته pop می کنیم.بعد از پیمایش رشته چون در حالت پایانی هستیم به محتوای پشته کاری نداریم و رشته پذیرفته میشه