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

سال ۸۷ -دو سوال

ارسال:
  

narges_r پرسیده:

سال ۸۷ -دو سوال

چرا در سوال ۶۲ L1 و L3 منظم هستن؟


چرا در سوال اول L(G زیر مجموعه L1 هست؟
من نمیتونم موردی رو پیدا کنم که L1 اونو قبول کنه اما L(G اونو قبول نکنه!
من هرچی برا خودم مثال زدم زبان L1 با زبان گرامر یکی شد.

فکر میکنم گرامر a^n b^2n a^n قبول نمیکنه اما L1 این رشته رو میپذیره
لطفا راهنمایی کنید


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


۱
ارسال:
  

Jooybari پاسخ داده:

دو سوال از سال ۸۷

درمورد سوال قبل چون S->SS نداریم رشته هایی مشابه aaabbbaaabbb و امثالش که برای تولید به این قاعده احتیاج دارن رو نمیشه با گرامر تولید کرد.
درمورد سوال ۶۲ اگه آلفا و گاما رو نال بگیریم و مقادیر i,j رو ۰ یا ۱ با توجه به فرضشون درنظر بگیریم که مغایرت هم نداشته باشه، در این صورت L1,L2 میشن سیکما استار و L3 میشه سیکما پلاس. همشون منظمن.

ارسال:
  

homa پاسخ داده:

RE: دو سوال از سال ۸۷

(۱۸ بهمن ۱۳۹۰ ۰۸:۴۸ ب.ظ)Lakikharin نوشته شده توسط:  درمورد سوال قبل چون S->SS نداریم رشته هایی مشابه aaabbbaaabbb و امثالش که برای تولید به این قاعده احتیاج دارن رو نمیشه با گرامر تولید کرد.
درمورد سوال ۶۲ اگه آلفا و گاما رو نال بگیریم و مقادیر i,j رو ۰ یا ۱ با توجه به فرضشون درنظر بگیریم که مغایرت هم نداشته باشه، در این صورت L1,L2 میشن سیکما استار و L3 میشه سیکما پلاس. همشون منظمن.
ولی L2 منظم نیست چون باید تعداد جمله‌ی آخر بر اساس دو رشته‌ی قبلی باشه و نه بیشتر و نه کمتر
یافتن تمامی ارسال‌های این کاربر

۱
ارسال:
  

Jooybari پاسخ داده:

دو سوال از سال ۸۷

گفتم که اگه آلفا و گاما رو نال درنظر بگیرین تمام رشته های زبانو میشه باهاش ساخت. با قراردادن j=0 رشته نال و با قرار دادن j=1 بقیه رشته‌ها با توجه به بتا تولید میشه..
فرض کنید زبانی داریم که رشته های بفرم W^i رو قبول میکنه که W سیکما استار و i بزرگتریامساوی یکه. میخایم ببینیم که این زبان چه رشته هایی رو قبول میکنه. W و WW و WWW و WWWW و WWW...WWW رشته هایی هستن که زبان تولید میکنه. اگه توجه کنید بخاطر سیکما استار بودن W تمام رشته هایی که از چند W تشکیل شده رو هم شامل میشه. یعنی تمام رشته هایی رو که میشه با WW یا WWWWW و ... ساخت رو با W هم میشه ساخت.
توی این سوال هم تونستیم رشته هارو به فرمی بنویسیم که تمام رشته های دیگه رو شامل بشه. یعنی رشته ای وجود نداشته باشه که توی زبان باشه و با یکی از چند حالت محدود مشخص نشه ساخت. البته باید توجه کنیم که این حالات مشخص با قرار دادن مقادیر لازم برای متغیرهاش ساخته بشن. تونستیم برای این رشته‌ها یه ماشین جدیدی پیدا کنیم که تمام حالات دیگه رو پوشش بده و میتونیم برای اون یه dfa بکشیم. پس منظمه.

۱
ارسال:
  

پشتکار پاسخ داده:

دو سوال از سال ۸۷

aabbaabb

این یکی رو که دیگه فکر نکنم

۰
ارسال:
  

narges_r پاسخ داده:

RE: دو سوال از سال ۸۷

جواب سوال دوممو فهمیدم پس فقط سوال ۶۲ میزارم


(۱۸ بهمن ۱۳۹۰ ۰۷:۵۸ ب.ظ)homa نوشته شده توسط:  
(18 بهمن ۱۳۹۰ ۰۷:۳۱ ب.ظ)narges_r نوشته شده توسط:  چرا در سوال اخر L1 و L3 منظم هستن؟


چرا در سوال اول L(G زیر مجموعه L1 هست؟
من نمیتونم موردی رو پیدا کنم که L1 اونو قبول کنه اما L(G اونو قبول نکنه!

لطفا راهنمایی کنید

من هم هرچی برا خودم مثال زدم زبان L1 با زبان گرامر یکی شد.
سوال هم گذاشتم

فکر میکنم گرامر a^n b^2n a^n قبول نمیکنه اما L1 این رشته رو میپذیره


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

ارسال:
  

homa پاسخ داده:

RE: دو سوال از سال ۸۷

در مورد گرامر L2 ما وابستگی توانی بین جمله‌ها داریم جمله اخر با دو تای اولی
اما در مورد گرامر L1 و L3 هر کدوم از جمله‌ها میتونن به تعداد دلخواه بیان و نه نیاز به حافظه داریم و نه وابستگی توانی دارن
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

narges_r پاسخ داده:

دو سوال از سال ۸۷

خوب مثلادر L1 الفا و گاما باید تعدادشون یکی باشه، چرا میگید که وابستگی توانی ندارند؟



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تشریح تست همروندی - بررسی یکی از سوالات سال ۸۲ abji22 ۵ ۱,۸۷۳ ۰۲ دى ۱۳۹۹ ۱۱:۰۵ ق.ظ
آخرین ارسال: mohammadasadi1
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۵ ۴,۲۶۳ ۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ
آخرین ارسال: s-taheri
  سوال ۸ دکتری علوم کامپیوتر سال ۹۴ ss311 ۲ ۱,۲۸۶ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۷ ب.ظ
آخرین ارسال: ss311
  جواب سوالهای تخصصی دکتری هوش مصنوعی سال ۹۸ Lootus ۱ ۱,۰۱۵ ۲۹ بهمن ۱۳۹۸ ۰۱:۴۳ ب.ظ
آخرین ارسال: machine86
  سوال مهندسی نرم افزار سال ۸۶(مهندسی نیازمندی ها) tarane1992 ۴ ۳,۰۵۷ ۲۲ بهمن ۱۳۹۷ ۰۲:۳۷ ق.ظ
آخرین ارسال: Bon_Nemesis
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۱۵ ۱۲,۴۲۸ ۱۹ آذر ۱۳۹۷ ۱۱:۱۰ ق.ظ
آخرین ارسال: *farnaz*
  بررسی سوالات ازمون دکترای سال ۹۷-گرایش هوش مصنوعی emranvfd ۳ ۱,۸۶۵ ۱۳ اسفند ۱۳۹۶ ۰۱:۱۰ ب.ظ
آخرین ارسال: robin
Rainbow بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار Seza ۲۸ ۸,۲۶۶ ۰۶ اسفند ۱۳۹۶ ۰۸:۰۸ ب.ظ
آخرین ارسال: Seza
  دوستانی که مایل به حل و تحلیل سوالات سال های اخیر الگوریتم هستند پیام بدن تحلیل کنیم robin ۱ ۱,۰۲۲ ۰۱ بهمن ۱۳۹۶ ۰۹:۵۹ ب.ظ
آخرین ارسال: h@3!n
  مجموعه سوالات استعداد تحصیلی و زبان و تخصصی هوش مصنوعی برای چند سال اخیر آزمون دکتری Jooybari ۱ ۲,۰۹۷ ۰۴ آذر ۱۳۹۶ ۰۸:۲۳ ب.ظ
آخرین ارسال: neilabak

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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