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

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

ارسال:
  

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 الفا و گاما باید تعدادشون یکی باشه، چرا میگید که وابستگی توانی ندارند؟



پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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