تالار گفتمان مانشت

با سلام

آیا قوانین پوچ یا [tex]A\rightarrow \lambda[/tex] در محاسبه پیچیدگی اعمال میشوند؟

سلام
بستگی به این داره که شما پیچیدگی گرامر رو چه جوری تعریف کنید
برای مثال اگر پیچیدگی رو طول قواعد در نظر بگیری(منظور تعداد پایانه ها و غیر پایانه های دو طرف هر قاعده می باشد)
اون موقع قانون پوچ تاثیر داره و حذفش باعث کاهش پیچیدگی میشه

(28 آبان 1392 11:14 ب.ظ)kaviresabz نوشته شده توسط: [ -> ]سلام
بستگی به این داره که شما پیچیدگی گرامر رو چه جوری تعریف کنید
برای مثال اگر پیچیدگی رو طول قواعد در نظر بگیری(منظور تعداد پایانه ها و غیر پایانه های دو طرف هر قاعده می باشد)
اون موقع قانون پوچ تاثیر داره و حذفش باعث کاهش پیچیدگی میشه

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

(28 آبان 1392 11:20 ب.ظ)zimenswall نوشته شده توسط: [ -> ]

(28 آبان 1392 11:14 ب.ظ)kaviresabz نوشته شده توسط: [ -> ]سلام
بستگی به این داره که شما پیچیدگی گرامر رو چه جوری تعریف کنید
برای مثال اگر پیچیدگی رو طول قواعد در نظر بگیری(منظور تعداد پایانه ها و غیر پایانه های دو طرف هر قاعده می باشد)
اون موقع قانون پوچ تاثیر داره و حذفش باعث کاهش پیچیدگی میشه

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

اگر اشتباه نکنم این چیزی که شما گذاشتی یکی از تمرین های لینزه برا محاسبه پیچیدگی زبان های مستقل از متن که البته شما شرط روی سیگما رو نذاشتین
اونجا سوال شده که 1- حذف قوانین بی فایده 2- حذف قوانین لاندا و 3 - حذف قوانین یکه باعث کاهش پیچیدگی میشه یا نه؟
در مورد 1 باعث کاهش پیچیدگی میشه
ولی در مورد 2 و 3 هر دوحالت ممکن یعنی نمیتوان به طور قطع گفت باعث کاهش میشه یا افزایش
البته در جواب سوال اصلی باید گفت که طبق این فرمول قوانین پوچ محاسبه می شود

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

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

(28 آبان 1392 11:45 ب.ظ)zimenswall نوشته شده توسط: [ -> ]

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

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

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

(28 آبان 1392 11:50 ب.ظ)kaviresabz نوشته شده توسط: [ -> ]

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

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

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

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

(29 آبان 1392 12:03 ق.ظ)zimenswall نوشته شده توسط: [ -> ]

(28 آبان 1392 11:50 ب.ظ)kaviresabz نوشته شده توسط: [ -> ]

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

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

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

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

درسته
شما خودتون با چنتا مثال میتونید به جواب برسید
برا کاهش پیچیدگی تو حالت حذف قوانین یکه داریم
A->aA
A->B
B->b
بعد از حذف قوانین یکه طبق فرمول پیچیدگی کاهش می یابد

(29 آبان 1392 12:36 ق.ظ)kaviresabz نوشته شده توسط: [ -> ]درسته
شما خودتون با چنتا مثال میتونید به جواب برسید
برا کاهش پیچیدگی تو حالت حذف قوانین یکه داریم
A->aA
A->B
B->b
بعد از حذف قوانین یکه طبق فرمول پیچیدگی کاهش می یابد

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

بابت راهنماییهاتون خیلی خیلی تشکر

و بالاخره فهمیدم که پیچیدگی برای قوانین تهی چی میشه
[tex]A\rightarrow \lambda[/tex]

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

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

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

(13 آذر 1392 08:27 ب.ظ)zimenswall نوشته شده توسط: [ -> ]و بالاخره فهمیدم که پیچیدگی برای قوانین تهی چی میشه
[tex]A\rightarrow \lambda[/tex]

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

کلا خیلی حال میده که آدم یه چیزی رو بعد از یه مدتی میفهمه که چی میشه! تبریک میگم.