(۱۱ اردیبهشت ۱۳۹۴ ۰۶:۰۳ ب.ظ)Hera نوشته شده توسط:  کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟

۱) تمامی رشته هایی که پنجمین سمبل آنها از راست ۰ است.
۲) مجموعه تمامی رشته هایی که به تعداد مساوی صفر و یک دارند.
۳) مجموعه تمامی رشته هایی که به عنوان یک عدد باینری بر ۱۲ بخش پذیرند.
۴) مجموعه تمامی رشته هایی که طول آنها ۱۲ است.


میدونم که گزینه ۲ منظم نیست.
ولی علت منظم بودن گزینه ۳ و ۴ رو میخوام بدونم.

همانطور که گفتید گزینه ۲ منظم نیست چون نمی توان با تعداد محدودی حالت تعداد صفرها و یک ها رو دنبال کرد ولی با پشته میشه.

با توجه به تصویر پیوست شده، می توان برای ۴ (تمرین لینز) یک dfa (یا nfa) رسم کرد و بنابراین منظم هستند. همچنین با جدا کردن حالات ۵ سمبل آخر یک رشته می توان یک dfa برای گزینه های ۱ (تمرین لینز) رسم کرد.
برای گزینه ۳ هم برای بخش پذیر بودن عدد بر ۱۲، کافی است چک کنیم عدد بر ۴ و ۳ بخش پذیر است. بخش پذیر بودن عدد بر ۴ که ساده است، باید دو بیت کم ارزش عدد صفر باشد تا بر ۴ بخش پذیر باشد. برای بخش پذیر بودن بر ۳ هم می توان یک dfa رسم کرد (تمرین لینز) و زبان های منظم هم تحت عمل اشتراک منظم هستند، بنابراین گزینه ۳ نیز منظم است.
اگر لازم است بگوئید تا dfa گزینه ۳ را نیز رسم کنم.