زمان کنونی: ۰۷ آذر ۱۴۰۳, ۰۷:۳۳ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تست سال ۸۱ علوم/ کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟

ارسال:
  

Hera پرسیده:

Question تست سال ۸۱ علوم/ کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟

کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟

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


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

۱
ارسال:
  

Farzamm پاسخ داده:

RE: تست سال ۸۱ علوم/ کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟

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

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


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

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

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


فایل‌(های) پیوست شده

مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Hera پاسخ داده:

RE: تست سال ۸۱ علوم/ کدامیک از زبانهای زیر روی الفبای {۰,۱} منظم نیست؟

مرسی!
اگه وقت کردین ممنون میشم که ب پ بر ۱۲ رو هم بکشین! Big Grin
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تشریح تست همروندی - بررسی یکی از سوالات سال ۸۲ abji22 ۵ ۵,۲۱۲ ۰۲ دى ۱۳۹۹ ۱۱:۰۵ ق.ظ
آخرین ارسال: mohammadasadi1
Wink دانلود نظریه زبانهای پیتر لینز ویرایش ۵ + حل armin.sheikh ۵ ۱۲,۲۳۹ ۰۲ خرداد ۱۳۹۹ ۰۸:۲۶ ب.ظ
آخرین ارسال: gillda
  سوال ۸ دکتری علوم کامپیوتر سال ۹۴ ss311 ۲ ۳,۴۸۸ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۷ ب.ظ
آخرین ارسال: ss311
  انجام پایان نامه برای داده کاوی استقرایی روی FIM ویافتن ARM با دوتا یا بیشتر CUDA GPU zaliabbass ۲ ۴,۴۴۲ ۰۶ اسفند ۱۳۹۸ ۰۸:۳۳ ب.ظ
آخرین ارسال: bankabzar
  منابع یوسفی تو ارشد اصلا جالب نیستن tesla66 ۱۳ ۸,۹۹۸ ۰۷ دى ۱۳۹۸ ۰۴:۳۲ ق.ظ
آخرین ارسال: marvelous
  نقش آفرینی بر روی پارچه در قدیم چگونه بوده است؟ maryamdolati ۰ ۷,۷۸۷ ۱۲ آذر ۱۳۹۸ ۰۵:۲۲ ب.ظ
آخرین ارسال: maryamdolati
Wink قبول شده های (علوم کامپیوتر، مهندسی کامپیوتر و IT ) سال ۹۸ اینجا اعلام کنند gaslakh ۲۵ ۱۶,۰۰۶ ۱۸ شهریور ۱۳۹۸ ۱۱:۳۰ ق.ظ
آخرین ارسال: mehdi.m2
  باز شدن یک دیکشنری با کلیک روی یک کلمه moslem73421 ۵ ۴,۷۳۲ ۰۴ مرداد ۱۳۹۸ ۰۷:۰۶ ب.ظ
آخرین ارسال: moslem73421
  گرامر منظم Sanazzz ۶ ۷,۰۴۵ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
Photo ساده سازی عبارت منظم etedadi ۰ ۲,۱۱۴ ۱۶ خرداد ۱۳۹۷ ۰۷:۰۴ ب.ظ
آخرین ارسال: etedadi

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close