(۱۳ آذر ۱۳۹۲ ۰۸:۲۷ ب.ظ)zimenswall نوشته شده توسط:  و بالاخره فهمیدم که پیچیدگی برای قوانین تهی چی میشه
[tex]A\rightarrow \lambda[/tex]

طبق فرمولی که گفته بودم پیچیدگی برای این قانون میشه ۰+۱ که میشه ۱
یعنی لانداها در پیچیدگی محاسبه میشوند ولی طولشان را صفر در نظر میگیریم و با یک جمع میکنیم

(۲۸ آبان ۱۳۹۲ ۱۱:۱۴ ب.ظ)kaviresabz نوشته شده توسط:  سلام
بستگی به این داره که شما پیچیدگی گرامر رو چه جوری تعریف کنید
برای مثال اگر پیچیدگی رو طول قواعد در نظر بگیری(منظور تعداد پایانه ها و غیر پایانه های دو طرف هر قاعده می باشد)
اون موقع قانون پوچ تاثیر داره و حذفش باعث کاهش پیچیدگی میشه

(۲۸ آبان ۱۳۹۲ ۱۱:۲۰ ب.ظ)zimenswall نوشته شده توسط:  

(28 آبان ۱۳۹۲ ۱۱:۱۴ ب.ظ)kaviresabz نوشته شده توسط:  سلام
بستگی به این داره که شما پیچیدگی گرامر رو چه جوری تعریف کنید
برای مثال اگر پیچیدگی رو طول قواعد در نظر بگیری(منظور تعداد پایانه ها و غیر پایانه های دو طرف هر قاعده می باشد)
اون موقع قانون پوچ تاثیر داره و حذفش باعث کاهش پیچیدگی میشه

منظور از پیچیدگی این عبارت هست.
[tex] Comp(G) = \sum (1 |V|)[/tex]

(۲۸ آبان ۱۳۹۲ ۱۱:۳۸ ب.ظ)kaviresabz نوشته شده توسط:  اگر اشتباه نکنم این چیزی که شما گذاشتی یکی از تمرین های لینزه برا محاسبه پیچیدگی زبان های مستقل از متن که البته شما شرط روی سیگما رو نذاشتین
اونجا سوال شده که ۱- حذف قوانین بی فایده ۲- حذف قوانین لاندا و ۳ - حذف قوانین یکه باعث کاهش پیچیدگی میشه یا نه؟
در مورد ۱ باعث پیچیدگی میشه
ولی در مورد ۲ و ۳ هر دوحالت ممکن یعنی نمیتوان به طور قطع گفت باعث کاهش میشه یا افزایش

(۲۸ آبان ۱۳۹۲ ۱۱:۴۵ ب.ظ)zimenswall نوشته شده توسط:  

(28 آبان ۱۳۹۲ ۱۱:۳۸ ب.ظ)kaviresabz نوشته شده توسط:  اگر اشتباه نکنم این چیزی که شما گذاشتی یکی از تمرین های لینزه برا محاسبه پیچیدگی زبان های مستقل از متن که البته شما شرط روی سیگما رو نذاشتین
اونجا سوال شده که ۱- حذف قوانین بی فایده ۲- حذف قوانین لاندا و ۳ - حذف قوانین یکه باعث کاهش پیچیدگی میشه یا نه؟
در مورد ۱ باعث پیچیدگی میشه
ولی در مورد ۲ و ۳ هر دوحالت ممکن یعنی نمیتوان به طور قطع گفت باعث کاهش میشه یا افزایش

یادم نیست کجا خوندم ولی چیزی که یادمه اینه که گفته شده بود:
۱/ حذف قوانین لاندا هم کاهش، افزایش و ثبات پیچیدگی را داره
۲/ حذف قوانین یکه فقط افزایش و ثبات پیچیدگی را داره و کاهش وجود نداره
۳/ حذف قوانین بی فایده همیشه باعث کاهش پیچیدگی میشه و ثابت اگر قانون بی فایده ای نباشه.

(۲۸ آبان ۱۳۹۲ ۱۱:۵۰ ب.ظ)kaviresabz نوشته شده توسط:  

(28 آبان ۱۳۹۲ ۱۱:۴۵ ب.ظ)zimenswall نوشته شده توسط:  یادم نیست کجا خوندم ولی چیزی که یادمه اینه که گفته شده بود:
۱/ حذف قوانین لاندا هم کاهش، افزایش و ثبات پیچیدگی را داره
۲/ حذف قوانین یکه فقط افزایش و ثبات پیچیدگی را داره و کاهش وجود نداره
۳/ حذف قوانین بی فایده همیشه باعث کاهش پیچیدگی میشه و ثابت اگر قانون بی فایده ای نباشه.

۱- پست قبلی رو ویرایش کردم
۲- من جوابو از روی حل تمرین لینز گذاشتم

(۲۹ آبان ۱۳۹۲ ۱۲:۰۳ ق.ظ)zimenswall نوشته شده توسط:  

(28 آبان ۱۳۹۲ ۱۱:۵۰ ب.ظ)kaviresabz نوشته شده توسط:  

(28 آبان ۱۳۹۲ ۱۱:۴۵ ب.ظ)zimenswall نوشته شده توسط:  یادم نیست کجا خوندم ولی چیزی که یادمه اینه که گفته شده بود:
۱/ حذف قوانین لاندا هم کاهش، افزایش و ثبات پیچیدگی را داره
۲/ حذف قوانین یکه فقط افزایش و ثبات پیچیدگی را داره و کاهش وجود نداره
۳/ حذف قوانین بی فایده همیشه باعث کاهش پیچیدگی میشه و ثابت اگر قانون بی فایده ای نباشه.

۱- پست قبلی رو ویرایش کردم
۲- من جوابو از روی حل تمرین لینز گذاشتم

ممنون از جوابتون.
اما در کل با توجه به همون فرمول پیچیدگی که گفتم آیا اون سه موردی که بالا گفتم صحیحه یا نه.
[tex]comp(G) = \sum_{}^{A\rightarrow V \in P}[/tex]
شرط سیگما به این صورت بود

گزینه ۳ که موردی نداره.
در گزینه های ۱و۲ افزایش و ثبات پیچیدگی هم موردی نداره.
فقط میمونه اینکه در گزینه های ۱و۲ در مورد کاهش پیچیدگی درست گفته شده یانه؟

(۲۹ آبان ۱۳۹۲ ۱۲:۳۶ ق.ظ)kaviresabz نوشته شده توسط:  درسته
شما خودتون با چنتا مثال میتونید به جواب برسید
برا کاهش پیچیدگی تو حالت حذف قوانین یکه داریم
A->aA
A->B
B->b
بعد از حذف قوانین یکه طبق فرمول پیچیدگی کاهش می یابد