برای زبان مستقل از متن L که به صورت زیر تعریف میشه چه جوری میتونیم با دو حالت و یک حالت پذیرش برای اون PDA طراحی کنیم:
L=مجموعه زبان های متشکل از a,b که تعدا aها فرد باشد و تعداد bها زوج
q(q0,a,0) \to q(q1,1)
q(q1,a,1) \to q(q0,1)
q(q0,a,1)\to q(q0,\lambda )
q(q0,a,0)\to q(q0,\lambda )
q(q0,b,0) \to q(q0,\lambda)
q(q0,b,0) \to q(q1,1)
q(q1,b,1)\to q(q2,1 )
q(q2,b,1)\to q(q0,\lambda )
q(q0,b,1)\to q(q0,\lambda )
(۲۱ بهمن ۱۳۹۰ ۰۲:۵۹ ب.ظ)sasanlive نوشته شده توسط:(21 بهمن ۱۳۹۰ ۰۱:۰۴ ب.ظ)homa نوشته شده توسط: برای زبان مستقل از متن L که به صورت زیر تعریف میشه چه جوری میتونیم با دو حالت و یک حالت پذیرش برای اون PDA طراحی کنیم:
L=مجموعه زبان های متشکل از a,b که تعدا aها فرد باشد و تعداد bها زوج
q0 الفبای a رو میخونه A رو تو پشته میذاره میره به خودش.
q0 الفبای a رو میخونه A رو از پشته بر میداره میره به خودش.
q0 الفبای b رو میخونه B رو تو پشته قرار میده میره به خودش.
q0 الفبای b رو میخونه B رو از پشته بر میداره میره به خودش.
q0 الفبای a رو میخونه هیچی تو پشته نمیذاره , هیچی هم بر نمیداره میره به q1.
q1 الفبای a رو میخونه A رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه A رو از پشته بر میداره میره به خودش.
q1 الفبای b رو میخونه B رو تو پشته قرار میده میره به خودش.
q1 الفبای b رو میخونه B رو از پشته بر میداره میره به خودش.
q1 پایانیه.
این الان یک NPDA (اتوماتای غیر قطعی)هست درسته ؟
اگه اینطوریه پس من بدون اینکه که پشته خالی بشه هم میتونم رشته رو بپذیرم و در این صورت رشته aa پذیرفته میشه
نقل قول: q0 الفبای b رو میخونه B رو تو پشته قرار میده میره به خودش.الان این PDA که تعریف کردین، aab رو میگیره. و ما هیچوقت هم از q1 به q0 بر نمی گردیم. یعنی هر ورودی که یک a داشته باشه پذیرفته میشه.
q0 الفبای b رو میخونه B رو از پشته بر میداره میره به خودش.
q0 الفبای a رو میخونه هیچی تو پشته نمیذاره , هیچی هم بر نمیداره میره به q1.
q1 الفبای a رو میخونه A رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه A رو از پشته بر میداره میره به خودش.
q1 الفبای b رو میخونه B رو تو پشته قرار میده میره به خودش.
q1 الفبای b رو میخونه B رو از پشته بر میداره میره به خودش.
q1 پایانیه.
(۲۱ بهمن ۱۳۹۰ ۰۵:۴۰ ب.ظ)shervinrs نوشته شده توسط: Stateی که در اون هستیم پذیرفته شدن یا نشدن رو تعیین میکنه، نه پر یا خالی بودن پشته.زمانی رشته ای پذیرفته می شه که دو شرط برقرار باشه:
۱- درحالت نهایی باشیم.
۲- پشته خالی شده باشه.
(۲۱ بهمن ۱۳۹۰ ۰۵:۴۴ ب.ظ)yaali نوشته شده توسط:اما شرط دوم رو که گفتید میشه از کتاب لینز آدرس بدید؟ در فصل هفتم تحت عنوان Definition 7.2 گفته شده که زبان پذیرفته شده توسط M رشته هایی که M رو در حالت نهایی قرار بدن و محتوی نهایی پشته اهمیتی در این مسئله نداره. البته این قبل از قسمت DPDA در مورد NPDA گفته شده. و در فصل DPDA هم فقط گفته شده که به ازای یک ورودی در یک حالت فقط یک انتقال داشته باشیم و شرطی برای وضعیت پشته نذاشته.(21 بهمن ۱۳۹۰ ۰۵:۴۰ ب.ظ)shervinrs نوشته شده توسط: Stateی که در اون هستیم پذیرفته شدن یا نشدن رو تعیین میکنه، نه پر یا خالی بودن پشته.زمانی رشته ای پذیرفته می شه که دو شرط برقرار باشه:
۱- درحالت نهایی باشیم.
۲- پشته خالی شده باشه.
یک سوال دیگه، این PDA تعریف شده ababa رو می پذیره؟ چون قابل قبول هست، اما فکر می کنم پشته خالی نمیشه.
منم فکر میکنم یه مشکلی هست و جوابش ناقصه !!!
q0 الفبای b رو میخونه B رو تو پشته قرار میده میره به خودش.
q0 الفبای b رو میخونه B رو از پشته بر میداره میره به خودش.
q0 الفبای a رو میخونه هیچی تو پشته نمیذاره , هیچی هم بر نمیداره میره به q1.
q1 الفبای a رو میخونه A رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه A رو از پشته بر میداره میره به خودش.
q1 الفبای b رو میخونه B رو تو پشته قرار میده میره به خودش.
q1 الفبای b رو میخونه B رو از پشته بر میداره میره به خودش.
q1 الفبای a رو میخونه C رو تو پشته میذاره میره به خودش.
q1 الفبای b رو میخونه C رو از پشته بر میداره D رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه D رو از پشته بر میداره E رو تو پشته میذاره میره به خودش.
q1 الفبای b رو میخونه E رو از پشته بر میداره میره به خودش.
q1 الفبای b رو میخونه F رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه F رو از پشته بر میداره G رو تو پشته میذاره میره به خودش.
q1 الفبای b رو میخونه G رو از پشته بر میداره H رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه H رو از پشته بر میداره میره به خودش.
q1 پایانیه.
(۲۱ بهمن ۱۳۹۰ ۱۱:۲۰ ب.ظ)sasanlive نوشته شده توسط: q1 الفبای a رو میخونه C رو تو پشته میذاره میره به خودش.چه دلیلی داشته که متغیر های دیگه رو استفاده کردین؟؟؟
q1 الفبای b رو میخونه C رو از پشته بر میداره D رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه D رو از پشته بر میداره E رو تو پشته میذاره میره به خودش.
q1 الفبای b رو میخونه E رو از پشته بر میداره میره به خودش.
q1 الفبای b رو میخونه F رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه F رو از پشته بر میداره G رو تو پشته میذاره میره به خودش.
q1 الفبای b رو میخونه G رو از پشته بر میداره H رو تو پشته میذاره میره به خودش.
q1 الفبای a رو میخونه H رو از پشته بر میداره میره به خودش.
q1 پایانیه.
(۲۱ بهمن ۱۳۹۰ ۱۱:۲۴ ب.ظ)homa نوشته شده توسط: چه دلیلی داشته که متغیر های دیگه رو استفاده کردین؟؟؟
چون زبانی مثله aabab رو نمیتونست اول تولید کنه.
وقتی a دوم رو میخوندیم A رو میذاشتیم تو پشته.
بعد b رو که میخوندیم B رو میذاشتیم تو پشته.
حالا میخواستیم a سومو بخونیم A زیر B در پشته قرار داشت و نمیتونستیم بکشیمش بیرون.