۱- برای طراحی pda آن کافیست به ازای هر a ای که در ورودی می بینیم دوتا a در پشته push کنیم و وقتی به b ها رسیدیم به ازای هر b یک a را از پسته pop کنیم این طوری هر a را با دو b تطبیق می دهیم و بعد هر چه c می بینیم رد می کنیم.

۲- برای طراحی pda آن کافی است به ازای هر دوa ای که می بینیم یک a در پشته push کنیم سپس به ازای هر b که در ورودی می بینیم یک a از پشته pop کنیم در این صورت هر دو a را با یک b تطبیق داده ایم بعد هر چه c می بینیم رد می کنیم

۳- رشته های زبا سوم بدین صورتند که در ابتدا یک سری a داریم و بعد یک سری c و تنها شرطی که باید داشته باشد این است که تعداد c ها باید زوج باشد پس منظم است و dfa آن به صورت زیر است.

زبان سوم منظم نیست و مستقل از متن است. مثلا رشته $aac^{100}$ عضو زبان سوم نمی باشد ولی عضو زبان ماشین طراحی شده در پاسخ شما می باشد.

در واقع به نظرم تعداد c ها در زبان سوم هر عدد زوجی هست که نصفش کمتر یا مساوی تعداد a ها باشه. پس نیاز است ماشین ما تعداد a ها رو به یاد داشته باشه و چون محدودیتی روی تعداد a ها نداریم، این کار نیاز به حافظه نا متناهی داره پس زبانش منظم نیست.

(۰۲ خرداد ۱۳۹۳ ۰۷:۳۷ ق.ظ)Morris نوشته شده توسط:  زبان سوم منظم نیست و مستقل از متن است. مثلا رشته $aac^{100}$ عضو زبان سوم نمی باشد ولی عضو زبان ماشین طراحی شده در پاسخ شما می باشد.

بله کاملا حق با شماست
ممنون