سلام دوستان
این سوال برای آزمون ۲۵ درصد دوم نصیر هست , اگه میشه لطف کنید درمورد الگوریتم CYK و روش حل این سوال توضیح بدید
به گرامر مستقل از متن زیر دقت کنید :
کد php:
S-> AB
A -> BB |a
B -> AB|b
۱-{A}
۲-تهی
۳-{S,B}
۴-{A,B}
برای استفاده از الگوریتم حتما باید گرامر به فرم نرمال چامسکی باشد ( که در اینجا هست) .در مرحله اول با توجه به رشته مورد نظر (V(ii رو پیدا می کنیم. منظور از Vii پایانه هایی هستند که می توانند حرف iام از رشته مورد نظر را تولید کنند .
برای این رشته :
کد:
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}این پاور پوینت هم خیلی مفیده .
[attachment=15097]