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

تعداد مراحل اشتقاق در یک گرامر مستقل از متن

ارسال:
  

mojgan پرسیده:

تعداد مراحل اشتقاق در یک گرامر مستقل از متن

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

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

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]


فایل‌(های) پیوست شده
ccc.docx
اندازه فایل: ۱۰/۶۷ KB

۰
ارسال:
  

mfXpert پاسخ داده:

مستقل از متن ؟

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  چرا مستقل از متنه؟ Wa^nb^mW^R poldasht ۱۱ ۱,۷۹۴ ۱۴ بهمن ۱۳۹۳ ۰۸:۱۰ ب.ظ
آخرین ارسال: ss.hoseini
  شمارش تعداد state های ماشین DFA mostafa2012 ۱۰ ۳,۱۷۷ ۱۳ بهمن ۱۳۹۳ ۱۱:۱۷ ق.ظ
آخرین ارسال: fatemeh69
  خواص مستقل از متن maryam.roshan ۳ ۱,۳۰۱ ۱۲ بهمن ۱۳۹۳ ۱۰:۰۱ ب.ظ
آخرین ارسال: fatemeh69
  تشخیص قطعی بودن ۴ زبان مستقل از متن MR.oracle ۹ ۲,۲۲۴ ۱۲ بهمن ۱۳۹۳ ۱۱:۲۳ ق.ظ
آخرین ارسال: ریحان
  چرا عکس نقیض لم تزریق مستقل از متن نشان دهنده نامنظم بودنه؟ ریحان ۷ ۱,۳۰۵ ۱۲ بهمن ۱۳۹۳ ۱۱:۱۳ ق.ظ
آخرین ارسال: ریحان
Question تشخیص زبان های مستقل از متن Ametrine ۹ ۲,۴۳۶ ۱۲ بهمن ۱۳۹۳ ۱۲:۵۱ ق.ظ
آخرین ارسال: ریحان
  چرا n(a)=!n(b) مستقل از متن قطعیه؟ ریحان ۸ ۱,۴۲۴ ۱۱ بهمن ۱۳۹۳ ۱۰:۰۲ ب.ظ
آخرین ارسال: ریحان
  آیا این زبان مستقل از متن است؟؟ K<=max(i,j) Imankhani ۸ ۱,۷۰۳ ۱۱ بهمن ۱۳۹۳ ۰۶:۴۷ ب.ظ
آخرین ارسال: ریحان
  تشخیص اجتماع و اشتراک یک زبان جساس به متن با مستقل از متن یا منظم maryam.roshan ۱ ۹۱۴ ۱۰ بهمن ۱۳۹۳ ۱۱:۴۳ ب.ظ
آخرین ارسال: fatemeh69
  آیا مستقل از متن قطعی است؟${a^mb^mc^n:0≤m≤n≤۲m\}$ archer22 ۳ ۱,۱۶۷ ۰۷ بهمن ۱۳۹۳ ۰۸:۰۲ ب.ظ
آخرین ارسال: Hamid_0311

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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