زمان کنونی: ۱۰ خرداد ۱۴۰۴, ۱۰:۰۱ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن میتوانید عضو شوید. گزینههای شما (ورود — ثبت نام)
فکر کنم خودم جوابو بدست آوردم:
DPDA ایی که پذیرشش با استک خالی باشه فقط زبان هایی را پذیرش میکنه که منظم باشه و هیچ رشته ای از زبان پیشوند زبان دیگر نباشد.
منظور از استک خالی چیه یعنی اینکه در اخر کار استک خالی باشه یا اینکه یعنی اصلا از استک استفاده نکنه
اگه اصلا از استک استفاده نکنه فک کنم باید زبان منظم باشه
بله(جواب سوال داخل پرانتز).
مثلا زبان a^nb^n یک زبان قطعی هست و با پشته خالی پذیرفته میشه.
نکته اینجاست که یکDPDA با پشته خالی نمیتونه تمام زبانهای قطعی و یا حتی بعضی زبانهای منظم رو بپذیره.
یعنی DPDA با پشته خالی قدرتش کمتر از DPDA با پشته پر هست.
استک خالی هم یعنی برای پذیرش رشته یکی از شرط هامون این باشه که پشته خالی بشه حتما.
برای بررسی مستقل از متن بودن توسط ماشین پشته ای خالی بودن پشته ملاک نیست بلکه شرط لازمه( اما نه شرط لازم و کافیه)
شرط لازم و کافی اینه که در حالی رشته ورودی به پایان رسیده پشته خالی باشه