سلام
سعی کنید برای این زبان یه گرامر بدید تا در مورد اش بحث کنیم.
الفبای این زبان فقط حرف a هست.
راهنمایی: باقیمانده ی تقسیم طول رشته به ۳ میتونه ۰، ۱ یا ۲ باشه، همچنین برای عدد ۲ باقی مانده های ۰ یا ۱ رو خواهیم داشت، باید گرامری بنویسیم که رشته هایی رو تولید کنه که طول اون رشته ها به نحوی باشه که اگر به ۳ تقسیم اش کنیم همون باقی مانده ای رو نده که وقتی به ۲ تقسیم اش می کنیم! مثلا اگر طول رشته ۶ باشه باقی مانده تقسیم اش به ۳ میشه ۰ و همچنین باقی مانده تقسیم اش به ۲ هم میشه ۰ پس قبول نیست! اما اگر طول رشته ۹ باشه باقی مانده تقسیم به ۳ اون میشه ۰ ولی باقی مانده تقسیم به ۲ اون میشه ۱
سوال ۱۵:
باقیمانده طول رشته بر ۳ نباید با باقیمانده طول رشته بر ۲ یکسان باشه.
باقیمانده بر ۲ شامل ۰ و ۱
باقیمانده بر ۳ شامل ۰و ۱و ۲
یعنی :
۱/ باقیمانده هر دو هم بر ۲ و هم بر ۳ ، همزمان نباید ۰و۱ باشند.
یعنی نباید طول رشته به صورت ۶k , 6k+1 باشه
۲/وقتیم که باقیمانده طول رشته بر ۳، دو بشه، مثل اعداد ۵،۸،۱۱،...همیشه شرط سوال رو دارند.که به صورت ۶k+2,6k+5 مباشند.
در مورد ۶k+3 ها که پس از ساده سازی همون مضرب ۳ ها هستن یاقیموندشون بر ۳ ، ۰ هست و تو مورد ۱ در نظر گرفتیم و اینجا لحاظش نمیکنیم.
طول ۲ و ۳ و ۴ و ۵ رو هم به تنهایی در نظر میگیریم( دلیل جدا کردن S , A)
پس نتیجه میشه:
[tex]S\rightarrow aaaaaaA|aa|aaa|aaaa|aaaaa[/tex]
[tex]A\rightarrow aaaaaaA|aa|aaaa|aaaaa[/tex]
(۲۱ خرداد ۱۳۹۲ ۱۲:۵۵ ق.ظ)reyhaneh64 نوشته شده توسط: یعنی :
یعنی نباید طول رشته به صورت ۶k , 6k+1 باشه
۲/وقتیم که باقیمانده طول رشته بر ۳، دو بشه، مثل اعداد ۵،۸،۱۱،...همیشه شرط سوال رو دارند.که به صورت ۶k+2,6k+5 مباشند.
در مورد ۶k+3 ها که پس از ساده سازی همون مضرب ۳ ها هستن یاقیموندشون بر ۳ ، ۰ هست و تو مورد ۱ در نظر گرفتیم و اینجا لحاظش نمیکنیم.
طول ۲ و ۳ و ۴ و ۵ رو هم به تنهایی در نظر میگیریم( دلیل جدا کردن S , A)
پس نتیجه میشه:
[tex]S\rightarrow aaaaaaA|aa|aaa|aaaa|aaaaa[/tex]
[tex]A\rightarrow aaaaaaA|aa|aaaa|aaaaa[/tex]
ممنون، من کمی روشن تر بگم ببینید منظورتون همینه، چهار حالت قابل قبول داریم که اینطور اند:
۱- وقتی باقیمانده ی بخش بر سه بشه ۰ و باقی مانده بخش بر دو بشه ۱
۲- وقتی باقیمانده ی بخش بر سه بشه ۱ و باقی مانده بخش بر دو بشه ۰
۳- وقتی باقیمانده ی بخش بر سه بشه ۲ و باقی مانده بخش بر دو بشه ۰
۴- وقتی باقیمانده ی بخش بر سه بشه ۲ و باقی مانده بخش بر دو بشه ۱
که از حالت اول شما ۶k+1 رو استخراج کردید، از حالت دوم هم احتمالا باید ۶k+4 رو نتیجه میگرفتید، از حالت سوم ۶k+2 و از حالت چهارم هم ۶k+5 رو استخراج کردید.
خب میخوام توضیح بدید اینکه اگر بخواهیم باقی مانده ی تقسیم بر ۳ بشه ۰ و باقی مانده تقسیم بر ۲ بشه ۱ چطور رابطه ی خطی مثل ۶k+3 به فکرمون برسه؟!
من این گرامر رو نوشتم
[tex]S\rightarrow aaaaaaA/A[/tex]
[tex]A\rightarrow aa/aaa[/tex]
من چند تا رشته رو مثال زدم برای خودم.
رشته با طول ۱ پذیرش نمیشه
رشته با طول ۲ پذیرش
رشته با طول ۳ پذیرش
رشته با طول ۴ پذیرش
رشته با طول ۵ پذیرش
رشته با طول ۶ پذیرش نمیشه
وقتی که حاصل تقیسم بر ۲ و ۳ بشه (۰ و ۱) رشته نباید پذیرش بشه. این اتفاق در مضارب ۶ می افته (۶k )که عدد هم بر ۳ و هم بر ۲ بخش پذیره و باقیمانده میشه ۰
و عدد بعدش یعنی (۶k+1 ) که باقیمانده ۱ میشه. از متغییر A کمک می گیریم تا اعداد بین دو مضرب۶ رو ایجاد کنیم البته به جز ۶K+1
(۲۱ خرداد ۱۳۹۲ ۰۹:۴۵ ب.ظ)هاتف نوشته شده توسط: ممنون، من کمی روشن تر بگم ببینید منظورتون همینه، چهار حالت قابل قبول داریم که اینطور اند:شماره ۱ تا ۴ درسته اما من اینجوری استدلال نکردم.
۱- وقتی باقیمانده ی بخش بر سه بشه ۰ و باقی مانده بخش بر دو بشه ۱
۲- وقتی باقیمانده ی بخش بر سه بشه ۱ و باقی مانده بخش بر دو بشه ۰
۳- وقتی باقیمانده ی بخش بر سه بشه ۲ و باقی مانده بخش بر دو بشه ۰
۴- وقتی باقیمانده ی بخش بر سه بشه ۲ و باقی مانده بخش بر دو بشه ۱
که از حالت اول شما ۶k+1 رو استخراج کردید، از حالت دوم هم احتمالا باید ۶k+4 رو نتیجه میگرفتید، از حالت سوم ۶k+2 و از حالت چهارم هم ۶k+5 رو استخراج کردید.
خب میخوام توضیح بدید اینکه اگر بخواهیم باقی مانده ی تقسیم بر ۳ بشه ۰ و باقی مانده تقسیم بر ۲ بشه ۱ چطور رابطه ی خطی مثل ۶k+3 به فکرمون برسه؟!
بعضی اوقات اگه سوالو یه جور دیگه تفسیرش کنیم جوابش ساده تر بدست میاد. مثلا اینجا به جای گفتن اینکه باقیمانده طول رشته بر ۳ با باقیمانده طول رشته بر ۲ یکی نباشه ، بگیم، چه وقت یکین؟ و گرامر یکی بودنو مینویسیم و حالات دیگرو یه جوری بهش اضافه میکنیم که تو شرط سوال بگنجن.
رابطه خطی، از این تغییر تفسیر بدست اومد.
باقیمانده تقسیم بر ۲ و بر ۳ وقتی یکین که یا باقیمانده هردو ۰ باشه یا باقیمانده هردو ۱/
باقیمانده هر دو بر ۲و ۳ وقتی ۰ میشه که بر ۶ بخشپذیر باشن و به همین ترتیب باقیمانده وقتی ۱ میشه که به شکل ۶k+1 باشن.
و حالات دیگه که شامل شرط سوال میشه:
۶k+2, 6k+3,6k+4,6k+5
که با استدلال ارسال قبلم ، ۶k+3 رو حذف کردم
(۲۱ خرداد ۱۳۹۲ ۱۰:۵۱ ب.ظ)Somayeh_Y نوشته شده توسط: من این گرامر رو نوشتمتو گرامی که نوشتین طول ۴و ۵ و ۱۰ و ۱۱و... پذیرش نمیشن.
[tex]S\rightarrow aaaaaaA/A[/tex]
[tex]A\rightarrow aa/aaa[/tex]
من چند تا رشته رو مثال زدم برای خودم.
رشته با طول ۱ پذیرش نمیشه
رشته با طول ۲ پذیرش
رشته با طول ۳ پذیرش
رشته با طول ۴ پذیرش
رشته با طول ۵ پذیرش
رشته با طول ۶ پذیرش نمیشه
وقتی که حاصل تقیسم بر ۲ و ۳ بشه (۰ و ۱) رشته نباید پذیرش بشه. این اتفاق در مضارب ۶ می افته (۶k )که عدد هم بر ۳ و هم بر ۲ بخش پذیره و باقیمانده میشه ۰
و عدد بعدش یعنی (۶k+1 ) که باقیمانده ۱ میشه. از متغییر A کمک می گیریم تا اعداد بین دو مضرب۶ رو ایجاد کنیم البته به جز ۶K+1
(۲۲ خرداد ۱۳۹۲ ۰۳:۳۰ ق.ظ)reyhaneh64 نوشته شده توسط: تو گرامی که نوشتین طول ۴و ۵ و ۱۰ و ۱۱و... پذیرش نمیشن.
مگه رابطه رو بازگشتی ننوشتم؟!!!
aaaa و aaaaa رو حذف کردم. چون با دوبار استفاده از متغییر A میشه طول ۴ و ۵ و ۱۰ و .... رو تولید کرد. تصورم بر اینه که هرچی گرامر کوتاه تر باشه بهینه تر هست.
فکر کنم حالا درست شده باشه.
[tex]s\rightarrow aaaaaaA/A[/tex]
[tex]A\rightarrow aaA/aaaA/aa/aaa[/tex]