با سلام دویاره
من در الگوریتم cyk دچا رمشکل هستم
ممنون میشم یکی از دوستان در رابطه با چگونگی اندیس گذاری متغییر‌ها راهنماییم کنه
تنها نمی دونم که این الگوریتم
i,k,j رو از کجا میاره
منتظر راهنماییتون هستم
الگوریتم CYK یک نمونه از الگوریتمهای برنامه نویسی پویاست و بنابراین با جدول سر و کار داره.
کتاب Linz عنصر خانه ij رو به این صورت تعریف کرده:
[
attachment=798]
یعنی برای خانه ij، تقاطع خانه های سطر i با خانه های ستون j به ترتیبی که مشخص شده باید در نظر گرفته شه: خانه اول سطر عنصر ij با خانه بعد از خانه عنصر در ستون این عنصر، خانه دوم سطر این عنصر با خانه بعدی در ستون این عنصر و ... تا وقتی در سطر این عنصر به خانه ij برسیم که کار رو در اینجا متوقف می کنیم.
این شکل خانه هایی که برای عنصر ij (خانه سبزرنگ) باید با هم در نظر گرفته بشن رو بهتر مشخص می کنه:
[
attachment=800]
منظورش از k چی هست؟
مرسی بابت پاسختون
از متغیر k برای حرکت روی خانه های سطر و ستون عنصر ij استفاده می شه. می تونید مثل متغیر یک حلقه for در نظر بگیریدش. یه شبه کد نه چندان دقیق برای نشون دادن عمل الگوریتم به این صورته:
کد:
for k = i to j-1 do
if X -> V[i,k]V[k+1,j] is a rule then
add X to V[i,j]
یعنی اگه از کنار هم گذاشتن دو متغیر خانه های ik و k+1,j یک قانون به صورت X->AB به دست اومد، X رو هم به V_ij اضافه کن (در هر خانه بیش از یک متغیر می تونه قرار بگیره).
فراموش نشه گرامر باید در فرم نرمال چامسکی باشه.
سلام
این الگوریتم cyk تا حالا ازش سوال اومده در کنکور؟
من از رو لینز یاد نگرفتم میتونین یه توضیح مختصر بدید؟
فقط در این حد اومده که پیچیدگی این الگوریتم برا پارس کردن یک رشته از چه مرتبه ای هست یا سوال هایی شبیه به این.همین تیپ از سوالات هم اکثرا تو کامپایلر اومده و نه تو نظریه
ممنون میشه لطف کنید بگید پیچیدگیش چی میشه ؟
میشه بیگ اوی طول رشته به توان سه
ممنون میشه یه توضیح کلی در مورد این الگوریتم هم بدید اصلا مفهوش چی هست ؟
این الگوریتم برای پارس یه رشته است که ببینه در زبان وجود داره یا نه . روش کارش خیلی راحته .
مثلا شما برای یه رشته‌ی خاص مثل aabcbb که می خواین ببینین در زبان وجود داره یا نه ابتدا گرامر رو به فرم نرمال چامسکی تبدیل می کنین .بعد یه جدول می کشین که پایین هر ستون یکی از این حروف به ترتیب نوشته شده .
بعد برای حرف اول میان می بینین مثلا a رو چه متغیر هایی از گرامر تولید می کنن . و اسم اون متغیر‌ها رو در خونه‌ی بالای a در جدول می نویسین.
بعد همین طور برای a بعدی . و برای b و c و ...
در مرحله‌ی بالاتر میاین روی متغیر‌ها بحث می کنین و مثلا اگه در خونه‌ی بالای a متغیر های S, A نوشته شده بود و طبعا در خونه‌ی بغلیشم که a هست همیناست . میاین می بینین که ترکیب این دوتا رو چه متغیری می سازه . مثلا ترکیب در اینجا SS,SA,AS,AA است. بعد اسم متغیر هایی که هر کدوم از اینا رو می سازن در سطر بالایی می نویسین . (تعداد خانه های سطر‌ها طبیعتا به صورت مثلثی کم می شه . چون در هر مرحله داریم دوتا دوتا با هم در نظر می گیریم) و همین طور برای دوتای بعدی و بعدی .
بعد به سطر بالاتر می ریم و همین کارو تکرار می کنیم .
در نهایت وقتی یه خونه بالا باقی موند اگر S در اون خونه قرار داشت این گرامر این رشته رو تولید می کنه و اگر نداشت تولید نمی کنه .
خیلی شهودی می تونین به درست بودن این الگوریتم پی ببرین .
مرتبه اجرای این الگوریتم مهمه بلد باشین که از n^3 هست.
امیدوارم فهمیده باشین
چون خیلی واضح توضیح ندادم . اگر سوالی بود در خدمتم .
سلام.
اگه امکان داره الگوریتمی که فرمودین را روی گرامر زیر مرحله به مرحله انجام بدین تا مطلب را بهتر بفهمیم.
خیلی ممنون.
S->aS|bB
B->bB|b
رشته ای هم که می خواهیم اشتقاق کنیم هست aabb
خب این گرامری که مثال زدین به فرم نرمال چامسکی نیست!! . فرم نرمال چامسکی دو نوع دستور مجاز هست توش .
a<--- A
AB<---- A
سرچ کردم الان این فایلو اگه نگاه کنین به صورت تصویری نشون داده
اگه سوالی هست در خدمتم .
ممنون از خانوم بچه مثبت اموزش جالب و کاملی بود یکی اگه میخاست این همه مطلب این پی دی اف رو تو تاپیک تایپ میکرد هم فهمش مشکل میشد هم توضیح دادنش سخت ولی این روش یادگیری بنظرم بهترین هست مرسی که پارسال اینو گذاشتی
ما از پارسالی ها هم که مطالب خوبی واسه ما گذاشتن تشکر میکنیم
بنظر من تمام بچه هایی که تو بحث الگوریتم شرکت کردند شایسته سپاس هستند...