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

سوال سال ۸۹ دانشگاه آزاد

ارسال:
  

mslinkin001 پرسیده:

سوال سال ۸۹ دانشگاه آزاد

با سلام خدمت دوستان سوال عکس زیر جوابش گزینه ی یک هست ( از روی دو منبع مختلف نگاه کردم هر دو گزینه ی یک رو زدن) ولی اصلا نمیفهمم چرا یک درسته.... هرجوری حساب میکنم هیچ گزینه ای درست نیست

[تصویر:  361913_4qug_n89.png]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

fatemeh69 پاسخ داده:

RE: سوال سال ۸۹ دانشگاه آزاد

سلام
گزینه ی یک صحیح است
زبان داده شده در صورت سوال متشکل از سه نوع رشته است:

دسته اول
[tex](\lambda a aa aaa)b^{\ast}[/tex] به معنای تمام رشته هایی است که در ابتدا حداکثر سه a دارند و بعد هیچی یا چند تا b در ادامه دارند

دسته دوم
[tex]a^{\ast}bbbbb^{\ast}[/tex] که به معنای تمام رشته هایی است که در ابتدا هیچ یا تعدادی a داند وبعد از آن حداقل ۴تا b دارند

دسته سوم
[tex](a b)^{\ast}ba(a b)^{\ast}[/tex] (البته تو سوال روی پرانتز دوم استار نداره که باید داشته باشه و اگه استار نداشته باشه هیچ گزینه ای صحیح نیست)
این دسته شامل تمام رشته هایی هستند که حداقل یک زیر رشته ی ba دارند یعنی حداقل در یک قسمتی از رشته b قبل از a ظاهر می شود.

حالا مکمل زبان گزینه ی اول را حساب کنیم
خود زیان می گه حتما تعداد a ها بزرگتر مساوی ۴ و حتما تعداد b ها باید کمتر مساوی ۳ باشه
نقیض آن می شه: رشته هایی که تعداد a ها کمتر ۴ (یعنی کمتر مساوی ۳: همون ردشته ی اولی که در بالا توضیح دادم) یا تعداد b ها باید بیشتر از ۳ (یعنی بیشتر مساوی ۴: همون دشته ی دوم) باشه
پس نقیض عبارت مطرح شده در زبان گزینه ی ی را می توان در رشته های دسته ی اول و دوم زبان مطرح شده در صورت سوال دید.

اما این دو دسته تمام زیان مکمل گزینه ی ۱ را تشکیل نمی دهند. چون معنای مکمل یک زیان یعنی تمام رشته هایی که در آن زیان نیستند مثلا در زیان گزینه ی ۱ همه ی رشته ها حتما بیشتر مساوی از ۴ تا a دارند پس همه ی رشته های با تعداد a های کمتر مساوی ۳ در مکمل این زبان هستند یا مثلا در زیان گزینه ی ۱ همه ی رشته ها حتما کمتر مساوی از ۳ تا b دارند پس همه ی رشته های با تعداد b های بیشتر مساوی ۴ در مکمل این زبان هستند
یا مثلا در همه ی رشته های زبان گزینه ی ۱ در ایتدا اول a ها آمده اند و بعد b ها و هیچ a ای حق ظاهر شدن بعد از b ها را ندارند . پس تمام رشته هایی که در آن ها حداقل یک بار یه a بعد از b ظاهر می شه در مکمل این زبان قرار دارند که همان رشته های دسته سوم هستند.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

gunnersregister پاسخ داده:

RE: سوال سال ۸۹ دانشگاه آزاد

گزینه ۲ غلطه: چون هر دو رشته [tex]\lambda[/tex] رو تولید میکنن. پس نمیتونن مکمل هم باشن.

گزینه ۳ غلطه: چون این زبان رشته [tex]ba[/tex] رو تولید نمیکنه.

گزینه ۴ غلطه: چون این زبان رشته [tex]ba[/tex] رو تولید نمیکنه.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

gunnersregister پاسخ داده:

RE: سوال سال ۸۹ دانشگاه آزاد

در توضیح گزینه ۱ :
قبل از هر چیز نمودار مربوطه به عبارت منظم [tex]aaaa(a)^{\ast}(\lambda b bb bbb)[/tex] را رسم میکنیم:


و حالا مکمل این زبان که در شکل دوم نمایش داده شده است:


و با تطبیق عبارت منظم و [tex]dfa[/tex] نهایی به نتیجه مطلوب میرسیم. البته مقایسه این دو (برابری زبان [tex]dfa[/tex] نهایی و زبان حاصل از عبارت منظم صورت سوال سخت است )

بهترین و راحتترین کار برای اینگونه سوالات رد کردن گزینه هاست.




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


نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۵ ۷,۳۱۴ ۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ
آخرین ارسال: s-taheri
  سوال ۸ دکتری علوم کامپیوتر سال ۹۴ ss311 ۲ ۳,۱۶۹ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۷ ب.ظ
آخرین ارسال: ss311
  معماری روزانه محقق اردبیلی یا دانشگاه آزاد علوم تحقیقات تهران aryaeei ۱۷ ۱۵,۸۷۱ ۱۷ شهریور ۱۳۹۸ ۰۱:۱۳ ق.ظ
آخرین ارسال: khayyam
  دانشگاه اراک و دانشگاه کاشان npour ۵ ۶,۱۷۶ ۲۲ خرداد ۱۳۹۸ ۱۰:۴۵ ب.ظ
آخرین ارسال: cpt.mazi
  سوال مهندسی نرم افزار سال ۸۶(مهندسی نیازمندی ها) tarane1992 ۴ ۴,۸۸۶ ۲۲ بهمن ۱۳۹۷ ۰۲:۳۷ ق.ظ
آخرین ارسال: Bon_Nemesis
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۱۵ ۱۷,۱۷۲ ۱۹ آذر ۱۳۹۷ ۱۱:۱۰ ق.ظ
آخرین ارسال: *farnaz*
  راهنمایی برای دانشگاه آزاد کرج Nilo_O ۱ ۲,۸۲۲ ۱۰ آبان ۱۳۹۷ ۰۳:۳۶ ب.ظ
آخرین ارسال: Nilo_O
Question شرایط انتقالی در دانشگاه آزاد amsl ۰ ۲,۳۶۳ ۲۸ مرداد ۱۳۹۷ ۰۱:۳۴ ق.ظ
آخرین ارسال: amsl
  کسی میدونه واحد های دانشگاه آزاد تا چه رتبه هایی از کنکور قبولی داشته پارسال ؟؟ liyana_m ۱ ۴,۹۵۷ ۲۹ خرداد ۱۳۹۷ ۰۳:۰۶ ب.ظ
آخرین ارسال: liyana_m
  سوال در مورد دانشگاه آزاد قزوین, ارشد شبکه های کامپیوتری networki ۰ ۲,۴۷۱ ۲۱ خرداد ۱۳۹۷ ۱۲:۵۳ ب.ظ
آخرین ارسال: networki

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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