سلام دوستان
در مورد این سوال نظری ندارید؟
با داشتن یه گرامر مستقل از متن و رشته ای به طول m از این گرامر بدترین زمان لازم برای یک الگوریتم تجزیه رشته ورودی روی این گرامر چیست؟
باید مشخص کنه که گرامر به چه فرمی هست!
خطی ساده
فرم نرمال چامسکی
فرم نرمال گریباخ
؟؟؟؟؟
میشه منو راهنمائی کنید به چه کتابی مراجعه کنم؟ یا به صورت کلی توضیحاتی بدید
خب وقتی گرامر مستقل از متن داری می تونی به دو نوع
1 گریباج
2 چامسکی
تبدیلش کمنی که هر کدام از این دو نوع یکی با 2n)-(2n-1_))پارس می کنه
تو این ادرس جزوه دکتر کارگهی را دانلود کنید و جزوه دکتر نوراله هم هست اونجا بهتر توضیح داده من حضور ذهن ندارم
- جزوه دست نویس ریاضیات مهندسی استاد کریمی
5- جزوه دست نویس ساختمان گسسته استاد نامور
6- جزوه دست نویس معماری کامپیوتر استاد یوسفی
7- جزوه دست نویس معماری کامپیوتر استاد نامور
8- جزوه دست نویس نظریه زبان هاو ماشینها استاد حاج سیدجوادی
9- جزوه دست نویس نظریه زبان هاو ماشینها استاد نورالله
10- جزوه دست نویس نظریه زبان هاو ماشینها استاد کارگهی
11- جزوه دست نویس سیستم عامل استاد سلیمی
12- جزوه دست نویس سیستم عامل استاد حقیقت
13- جزوه دست نویس مدار منطقی استاد نامور
14- جزوه تایپ شده ساختمان داده‌ها و الگوریتم های استاد قدسی
15- جزوه تایپ شده طراحی الگوریتم استاد حاج سید جوادی
16- جزوه تایپ شده طراحی زبانها استاد قبایی
17- جزوه تایپ شده پایگاه داده‌ها استاد عرب نژاد
18- جزوه تایپ شده طراحی کامپایلر استاد پارسا
که تو همین تایپیک‌ها بود
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
از این ادرس سایت رو باز کنید؟
اینها مربوط میشه به قسمت تجزیه و درخت اشتقاق
تجزیه یعنی ما میایم یه اشتقاق رو بررسی میکنیم اگه به رشته نرسیدیم یه اشتقاق دیگه رو بررسی میکنیم و الی آخر.
در فرم نرمال چامسکی با استفاده از الگوریتم CYK در زمان m^3 میتوان مشخص نمود که رشته عضو زبان هست یا خیر!
در فرم گریباخ الگوریتم خاصی نداریم.
در فرم گرامر ساده هم تجزیه حداکثر در m مرحله انجام میشود.
احتمالا جواب این سوال m^3 میشه البته اگه گزینه هایی مثل تصمیم ناپذیر و ... نداشته باشیم.
آقا صادق این 2n-1 برای فرم نرمال چامسکی مراحل تولید(اشتقاق) یک رشته است و با تجزیه فرق داره.
برای گرامرهای ساده و گریباخ هم مراحل تولید n هست.
خوب من چون عجله ای بود صورت سوال را خوب نخوندم.
تو فصل تورینگ یادتون هست که وقتی می خواستیم یه رشته را بگیم با این ماشین قبول می کنه یا نه حالا می گفتیم با این ماشین زمان رو می برهn2
تو اینجا هم همینطوره باید رشته مورد نظر را به ما بدهتند تا ما بتونیم بگیم که با این ماشین یاپشته مون چه قدره می تونیم قبولش کنیم.
نه اگر مشخص کند که گرامر ساده است که میشه n و اگر هم بگن چامسکی میشه n^3 در بقیه حالات باید رشته یا گرامر رو بهمون بدن.
فکر کنم این سوال از تمرینات لینز هست تو حل تمرین رو بررسی کن