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

سلام و خسته نباشید به همه بچه درس خونها
البته خودم جزوشون نیستم !

هر کسی می تونه در مورد این سوال توضیح بده
من پیشاپیش و پساپس تشکر می کنم

G گرامر مستقل از متن است که هیچ قانونی به شکل A →λ یا A →B به طوریکه [tex]A,\: B\in V[/tex] نداشته باشد
در اینصورت برای تشخیص رشته [tex]w\in L(G)[/tex] با استفاده از روش پویش کامل حداکثر چه تعداد شبه جمله ایجا د می گردد ؟

پاسخ:
[tex]\sum^{2|w|}_{i=0}(|p|)^i[/tex]

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