سلام دوستان
داشتم سوالای سالهای اخیر رو بررسی میکردم تو کتاب نصیر یه نتیجه گیری کرد
گفته: "برای هر زبان مستقل از متن می توان یه PDA با حداکثر دو حالت ساخت"!!!
مثلا برای زبان [tex]\{a^nb^n\: :\: n\ge0\}[/tex] چطور میشه با دوتا استیت PDA کشید؟!
اگر نظری دارید از سردرگمی درم بیارین
پیشاپیش ممنون از نظر دوستان
(۲۲ اسفند ۱۳۹۵ ۱۱:۳۸ ق.ظ)signal_micro نوشته شده توسط: سلام دوستان
داشتم سوالای سالهای اخیر رو بررسی میکردم تو کتاب نصیر یه نتیجه گیری کرد
گفته: "برای هر زبان مستقل از متن می توان یه PDA با حداکثر دو حالت ساخت"!!!
مثلا برای زبان [tex]\{a^nb^n\: :\: n\ge0\}[/tex] چطور میشه با دوتا استیت PDA کشید؟!
اگر نظری دارید از سردرگمی درم بیارین
پیشاپیش ممنون از نظر دوستان
سلام
ماشین های متفاوتی میشه کشید
مثلا این یکیش
(۲۲ اسفند ۱۳۹۵ ۱۲:۲۰ ب.ظ)delete4all نوشته شده توسط: سلاممرسی delete جان
ماشین های متفاوتی میشه کشید
مثلا این یکیش
فقط یه چیزی ...
الان این زبان [tex]a^3b^1[/tex] رو (فرضا) نمی پذیره؟ چون فقط در حالتی ماشین پذیرش میکنه که هم پشته خالی شده باشه و هم ورودی؟(با این فرض این ماشین درسته؟ وگرنه با ۳ تا a و یه b هم می پذیره!) ما آخر همه ماشینهامون یه یال میزدیم با برچسب [tex]\lambda,z,,z[/tex] یعنی اگر ورودی تموم شد و پشته خالی شد اونوقت برو به فاینال استیت الان فکر کنم اون استیت آخر زیادیه(اگه فرض کنیم فقط در حالتی ماشین پذیرش کنه که هم پشته خالی شده باشه و هم ورودی) و میشه هر زبانی رو با همون ۲تا استیت کشید
الان حرفام درسته؟ یا دارم باز جایی رو اشتباه میکنم؟
(۲۲ اسفند ۱۳۹۵ ۱۲:۴۸ ب.ظ)signal_micro نوشته شده توسط:(22 اسفند ۱۳۹۵ ۱۲:۲۰ ب.ظ)delete4all نوشته شده توسط: سلاممرسی delete جان
ماشین های متفاوتی میشه کشید
مثلا این یکیش
فقط یه چیزی ...
الان این زبان [tex]a^3b^1[/tex] رو (فرضا) نمی پذیره؟ چون فقط در حالتی ماشین پذیرش میکنه که هم پشته خالی شده باشه و هم ورودی؟(با این فرض این ماشین درسته؟ وگرنه با ۳ تا a و یه b هم می پذیره!) ما آخر همه ماشینهامون یه یال میزدیم با برچسب [tex]\lambda,z,,z[/tex] یعنی اگر ورودی تموم شد و پشته خالی شد اونوقت برو به فاینال استیت الان فکر کنم اون استیت آخر زیادیه(اگه فرض کنیم فقط در حالتی ماشین پذیرش کنه که هم پشته خالی شده باشه و هم ورودی) و میشه هر زبانی رو با همون ۲تا استیت کشید
الان حرفام درسته؟ یا دارم باز جایی رو اشتباه میکنم؟
خواهش میکنم
نه دیگه نبایدم [tex]a^3b^1[/tex] رو بپذیره
تو سوال گفته [tex]a^nb^n[/tex] و ینی به تعداد a باید b وجود داشته باشه دقیق به اندازه هم
استیت اول پایانی هست تا اگه مقدار n صفر بود ( ینی هیچی a و هیچی b) اونموقع پایان باشه
و استیت دوم هم پایانیه برای پایان بعد از آخرین ورود b دیگه
شکل های دیگم میشه کشید براش ، بنظرم اینم یه شکلشه: