کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟
۱) تمامی رشته هایی که پنجمین سمبل آنها از راست ۰ است.
۲) مجموعه تمامی رشته هایی که به تعداد مساوی صفر و یک دارند.
۳) مجموعه تمامی رشته هایی که به عنوان یک عدد باینری بر ۱۲ بخش پذیرند.
۴) مجموعه تمامی رشته هایی که طول آنها ۱۲ است.
میدونم که گزینه ۲ منظم نیست.
ولی علت منظم بودن گزینه ۳ و ۴ رو میخوام بدونم.
(۱۲ اردیبهشت ۱۳۹۴ ۱۲:۱۴ ق.ظ)Farzamm نوشته شده توسط:(11 اردیبهشت ۱۳۹۴ ۰۶:۰۳ ب.ظ)Hera نوشته شده توسط: کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟
۱) تمامی رشته هایی که پنجمین سمبل آنها از راست ۰ است.
۲) مجموعه تمامی رشته هایی که به تعداد مساوی صفر و یک دارند.
۳) مجموعه تمامی رشته هایی که به عنوان یک عدد باینری بر ۱۲ بخش پذیرند.
۴) مجموعه تمامی رشته هایی که طول آنها ۱۲ است.
میدونم که گزینه ۲ منظم نیست.
ولی علت منظم بودن گزینه ۳ و ۴ رو میخوام بدونم.
از کجا می دونید ۲ منظم نیست؟ اتفاقاً منظم است.
همانطور که در تصاویر پیوست شده مشخص است، می توان برای گزینه های ۱، ۲ و ۴ یک dfa (یا nfa) رسم کرد و بنابراین منظم هستند.
برای گزینه هم برای بخش پذیر بودن عدد بر ۱۲، کافی است چک کنیم عدد بر ۴ و ۳ بخش پذیر است. بخش پذیر بودن عدد بر ۴ که ساده است، باید دو بیت کم ارزش عدد صفر باشد تا بر ۴ بخش پذیر باشد. ولی ...
من تصویری نمیبینم؟!
(۱۱ اردیبهشت ۱۳۹۴ ۰۶:۰۳ ب.ظ)Hera نوشته شده توسط: کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟
۱) تمامی رشته هایی که پنجمین سمبل آنها از راست ۰ است.
۲) مجموعه تمامی رشته هایی که به تعداد مساوی صفر و یک دارند.
۳) مجموعه تمامی رشته هایی که به عنوان یک عدد باینری بر ۱۲ بخش پذیرند.
۴) مجموعه تمامی رشته هایی که طول آنها ۱۲ است.
میدونم که گزینه ۲ منظم نیست.
ولی علت منظم بودن گزینه ۳ و ۴ رو میخوام بدونم.
همانطور که گفتید گزینه ۲ منظم نیست چون نمی توان با تعداد محدودی حالت تعداد صفرها و یک ها رو دنبال کرد ولی با پشته میشه.
با توجه به تصویر پیوست شده، می توان برای ۴ (تمرین لینز) یک dfa (یا nfa) رسم کرد و بنابراین منظم هستند. همچنین با جدا کردن حالات ۵ سمبل آخر یک رشته می توان یک dfa برای گزینه های ۱ (تمرین لینز) رسم کرد.
برای گزینه ۳ هم برای بخش پذیر بودن عدد بر ۱۲، کافی است چک کنیم عدد بر ۴ و ۳ بخش پذیر است. بخش پذیر بودن عدد بر ۴ که ساده است، باید دو بیت کم ارزش عدد صفر باشد تا بر ۴ بخش پذیر باشد. برای بخش پذیر بودن بر ۳ هم می توان یک dfa رسم کرد (تمرین لینز) و زبان های منظم هم تحت عمل اشتراک منظم هستند، بنابراین گزینه ۳ نیز منظم است.
اگر لازم است بگوئید تا dfa گزینه ۳ را نیز رسم کنم.
مرسی!
اگه وقت کردین ممنون میشم که ب پ بر ۱۲ رو هم بکشین!
