۰
subtitle
ارسال: #۱
PDA
سلام دوستان
داشتم سوالای سالهای اخیر رو بررسی میکردم تو کتاب نصیر یه نتیجه گیری کرد
گفته: "برای هر زبان مستقل از متن می توان یه PDA با حداکثر دو حالت ساخت"!!!
مثلا برای زبان [tex]\{a^nb^n\: :\: n\ge0\}[/tex] چطور میشه با دوتا استیت PDA کشید؟!
اگر نظری دارید از سردرگمی درم بیارین
پیشاپیش ممنون از نظر دوستان
داشتم سوالای سالهای اخیر رو بررسی میکردم تو کتاب نصیر یه نتیجه گیری کرد
گفته: "برای هر زبان مستقل از متن می توان یه PDA با حداکثر دو حالت ساخت"!!!
مثلا برای زبان [tex]\{a^nb^n\: :\: n\ge0\}[/tex] چطور میشه با دوتا استیت PDA کشید؟!
اگر نظری دارید از سردرگمی درم بیارین
پیشاپیش ممنون از نظر دوستان
۰
ارسال: #۲
RE: PDA
(۲۲ اسفند ۱۳۹۵ ۱۱:۳۸ ق.ظ)signal_micro نوشته شده توسط: سلام دوستان
داشتم سوالای سالهای اخیر رو بررسی میکردم تو کتاب نصیر یه نتیجه گیری کرد
گفته: "برای هر زبان مستقل از متن می توان یه PDA با حداکثر دو حالت ساخت"!!!
مثلا برای زبان [tex]\{a^nb^n\: :\: n\ge0\}[/tex] چطور میشه با دوتا استیت PDA کشید؟!
اگر نظری دارید از سردرگمی درم بیارین
پیشاپیش ممنون از نظر دوستان
سلام
ماشین های متفاوتی میشه کشید
مثلا این یکیش
ارسال: #۳
RE: PDA
(۲۲ اسفند ۱۳۹۵ ۱۲:۲۰ ب.ظ)delete4all نوشته شده توسط: سلاممرسی delete جان
ماشین های متفاوتی میشه کشید
مثلا این یکیش
فقط یه چیزی ...
الان این زبان [tex]a^3b^1[/tex] رو (فرضا) نمی پذیره؟ چون فقط در حالتی ماشین پذیرش میکنه که هم پشته خالی شده باشه و هم ورودی؟(با این فرض این ماشین درسته؟ وگرنه با ۳ تا a و یه b هم می پذیره!) ما آخر همه ماشینهامون یه یال میزدیم با برچسب [tex]\lambda,z,,z[/tex] یعنی اگر ورودی تموم شد و پشته خالی شد اونوقت برو به فاینال استیت الان فکر کنم اون استیت آخر زیادیه(اگه فرض کنیم فقط در حالتی ماشین پذیرش کنه که هم پشته خالی شده باشه و هم ورودی) و میشه هر زبانی رو با همون ۲تا استیت کشید
الان حرفام درسته؟ یا دارم باز جایی رو اشتباه میکنم؟
ارسال: #۴
RE: PDA
(۲۲ اسفند ۱۳۹۵ ۱۲:۴۸ ب.ظ)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 دیگه
شکل های دیگم میشه کشید براش ، بنظرم اینم یه شکلشه:
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close