۰
subtitle
ارسال: #۱
سوال در مورد الگوریتم CYK
سلام دوستان
این سوال برای آزمون ۲۵ درصد دوم نصیر هست , اگه میشه لطف کنید درمورد الگوریتم CYK و روش حل این سوال توضیح بدید
به گرامر مستقل از متن زیر دقت کنید :
aabbb برای رشته V23 که عضویت یک رشته را در گرامر های مستقل از متن مشخص میکند , طبق الگوریتم CYK برابر است با:
۱-{A}
۲-تهی
۳-{S,B}
۴-{A,B}
این سوال برای آزمون ۲۵ درصد دوم نصیر هست , اگه میشه لطف کنید درمورد الگوریتم CYK و روش حل این سوال توضیح بدید
به گرامر مستقل از متن زیر دقت کنید :
کد php:
S-> AB
A -> BB |a
B -> AB|b
۱-{A}
۲-تهی
۳-{S,B}
۴-{A,B}
۱
ارسال: #۲
RE: سوال در مورد الگوریتم CYK
برای استفاده از الگوریتم حتما باید گرامر به فرم نرمال چامسکی باشد ( که در اینجا هست) .در مرحله اول با توجه به رشته مورد نظر (V(ii رو پیدا می کنیم. منظور از Vii پایانه هایی هستند که می توانند حرف iام از رشته مورد نظر را تولید کنند .
برای این رشته :
حالا برای پیدا کردن V12 از V11 و V22 کمک می گیریم ، یعنی آن ها را ترکیب می کنیم و معادل ترکیبشان را در هر پایانه ای دیدیم ، آن پایانه را می نویسیم. منظور از ترکیب این است :
در این سوال ما V23 را نیاز داریم . با کمک V22 و V33 :
V23 باید شامل پایانه ای باشه که AB رو تولید کنه . AB هم در S و هم در B تولید میشه
این پاور پوینت هم خیلی مفیده .
برای این رشته :
کد:
V11={A}
V22={A}
V33={B}
V44={B}
V55={B}حالا برای پیدا کردن V12 از V11 و V22 کمک می گیریم ، یعنی آن ها را ترکیب می کنیم و معادل ترکیبشان را در هر پایانه ای دیدیم ، آن پایانه را می نویسیم. منظور از ترکیب این است :
کد:
Vii={X,Y}
Vjj={W,Z}
ij :
(XW,XZ,YW,YZ)V23 باید شامل پایانه ای باشه که AB رو تولید کنه . AB هم در S و هم در B تولید میشه
کد:
V23={S,B}این پاور پوینت هم خیلی مفیده .
| CYK-Algorithm.ppt |
|
|
| اندازه فایل: ۸۷۹/۵ KB | ||
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close