سلام و درود دوستان .. این سوال رو میشه توضیح بدین دوستان..
یک رشته مخصوص به این صورت تعریف میشود :
-a یک رشته ی مخصوص است .
-اگر s یک رشته ی مخصوص باشد، Sa و Sbb نیز رشته های مخصوص هستند.
تعداد رشته های مخصوص که دقیقا از ۷ حرف تشکیل شده اند چند تاست ؟
سوال ۹۵ کتاب پوران از فصل شمارش ..
ممنون دوستان
سلام.گرامر این زبان تو درس نظریه ، S-->Sa|Sbb|a هستش.که با اشتقاقش میتونید،رشته های تولید شدشو مشاهده کنید.
با دو روش حل میکنم:
روش اول )شمارش:
ببینید گفته که حرف اول رشته،a هستش.پس ۶ تا حرف دیگه میمونه.
که میتونه از ۶ تا a تشکیل شده باشه:که چون یکسانند.چیدنش فقط ۱حالت داره.( !۶/! ۶) =۱
میتونه از ۴ تا a و یک bb تشکیل بشه : که جوابش میشه ( !۱ !۴/!۵ ) =۵
میتونه از ۲تا a و ۲تا bb تشکیل بشه : که جوابش میشه ( !۲ !۲/!۴ ) = ۶
و میتونه از ۳ تا bb تشکیل بشه : که جوابش میشه ( !۳/!۳ ) =۱
نکته:bb رو یک حرف در نظر میگیریم.
جواب نهایی میشه =۱+۶+۵+۱ = ۱۳
روش دوم ) بازگشتی:
اگه حرف اول a باشه، با an-1 حالت میتونیم رشته تولید کنیم.
ولی اگه حرف اول b باشه،حرف دوم هم باید b باشه ، که میشه bb ، که بعدش با an-2 حالت دیگه میتونیم رشته تولید کنیم.
پس یعنی an=an-1 + an-2 (سری فیبوناتچی)
a0=1 ، چونکه رشته ما بایستی با a شروع بشه،ما بصورت پیشفرض a0=1 قرار میدیم.ما بقیه رشته جدید رو باید بچینیم.
a1=1 ،اگه رشته یک حرفی باشه،یعنی a
a2=2،اگه رشته دو حرفی باشه، یعنی aو a یا bb
a3=a2+a1=3
a4=a3+a2=5
a5=a4+a3=8
a6=a5+a4=13
(۱۸ آبان ۱۳۹۴ ۰۴:۵۷ ب.ظ)IranianWizard نوشته شده توسط: سلام.گرامر این زبان تو درس نظریه ، S-->Sa|Sbb|a هستش.که با اشتقاقش میتونید،رشته های تولید شدشو مشاهده کنید.
با دو روش حل میکنم:
روش اول )شمارش:
ببینید گفته که حرف اول رشته،a هستش.پس ۶ تا حرف دیگه میمونه.
که میتونه از ۶ تا a تشکیل شده باشه:که چون یکسانند.چیدنش فقط ۱حالت داره.( !۶/! ۶) =۱
میتونه از ۴ تا a و یک bb تشکیل بشه : که جوابش میشه ( !۱ !۴/!۵ ) =۵
میتونه از ۲تا a و ۲تا bb تشکیل بشه : که جوابش میشه ( !۲ !۲/!۴ ) = ۶
و میتونه از ۳ تا bb تشکیل بشه : که جوابش میشه ( !۳/!۳ ) =۱
نکته:bb رو یک حرف در نظر میگیریم.
جواب نهایی میشه =۱+۶+۵+۱ = ۱۳
روش دوم ) بازگشتی:
اگه حرف اول a باشه، با an-1 حالت میتونیم رشته تولید کنیم.
ولی اگه حرف اول b باشه،حرف دوم هم باید b باشه ، که میشه bb ، که بعدش با an-2 حالت دیگه میتونیم رشته تولید کنیم.
پس یعنی an=an-1 + an-2 (سری فیبوناتچی)
a0=1 ، چونکه رشته ما بایستی با a شروع بشه،ما بصورت پیشفرض a0=1 قرار میدیم.ما بقیه رشته جدید رو باید بچینیم.
a1=1 ،اگه رشته یک حرفی باشه،یعنی a
a2=2،اگه رشته دو حرفی باشه، یعنی aو a یا bb
a3=a2+a1=3
a4=a3+a2=5
a5=a4+a3=8
a6=a5+a4=13
خیلی خیلی ممنونم از راهنمایی وتوضیحتون .. به نظرتون چه کتابی برای نظریه ی زبان ها مناسبه برای کنکور که حالت خودآموز هم داشته باشه .. ممنون میشم معرفی کنید .. من نظریه پاس نکردم .. !
(۱۹ آبان ۱۳۹۴ ۰۴:۴۲ ق.ظ)mahdi.d نوشته شده توسط: خیلی خیلی ممنونم از راهنمایی وتوضیحتون .. به نظرتون چه کتابی برای نظریه ی زبان ها مناسبه برای کنکور که حالت خودآموز هم داشته باشه .. ممنون میشم معرفی کنید .. من نظریه پاس نکردم .. !خواهش میکنم
اگه نظریه رو پاس نکردین،بنظرم حتما بایستی کتاب لینز رو مطالعه کنید.و بعدش از همه مهمتر تمریناتشو حل کنید.
(۱۹ آبان ۱۳۹۴ ۰۵:۱۳ ق.ظ)IranianWizard نوشته شده توسط:(19 آبان ۱۳۹۴ ۰۴:۴۲ ق.ظ)mahdi.d نوشته شده توسط: خیلی خیلی ممنونم از راهنمایی وتوضیحتون .. به نظرتون چه کتابی برای نظریه ی زبان ها مناسبه برای کنکور که حالت خودآموز هم داشته باشه .. ممنون میشم معرفی کنید .. من نظریه پاس نکردم .. !خواهش میکنم
اگه نظریه رو پاس نکردین،بنظرم حتما بایستی کتاب لینز رو مطالعه کنید.و بعدش از همه مهمتر تمریناتشو حل کنید.
ممنون و سپاس گزار از وقتی گذاشتین بنده چون ناپیوسته بود کارشناسیم سه درس محاسبات عددی ، کاپمایلر و نظریه رو پاس نکردم .. میبخشیئ که دوباره سوال میکنم .. به نظرتون برای این درسا رفرنس بخونم تا مهلت باقی مونده تا کنکور ارشد و همراهشون کتاب تست بگیرم یا صرفا کتاب تست کفایت میکنه ؟ به نظرتون پوران خوبه یا پارسه یا غیره ؟ اگه میشه توضیح بفرمایید .. بسیار سپاس