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