هل نتيجة محلل CYK صحيحة؟

Question

أحاول أن أتعلم خوارزمية تحليل CYK.

بالنسبة لهذه المجموعة من القواعد النحوية، هل الجداول الناتجة صحيحة بالنسبة للجملتين المعطاتين؟

S -> NP VP
VP -> VB NP
NP -> DT NN
PP -> IN NP
NP -> NP PP
NP -> NN
VP -> VP PP
IN -> with
NN -> dog
NN -> cat
VB -> ate
NN -> mouse
DT -> the


['S']
[None, None]
[None, None, 'VP']
['NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog']


['S']
['NP', None]
['NP', None, 'VP']
['NP', None, None, 'NP']
[None, None, 'VP', None, None]
[None, None, 'VP', None, None, 'PP']
['NP', None, None, 'NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN', 'IN', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog', 'with', 'the', 'cat']

Answer 1

يمكنك محاولة تقليل قواعدك النحوية أولاً، لأن هناك بعض القواعد غير الضرورية، علاوة على ذلك، هذا هو السبب not in CNF.

إذا نظرنا إليها بشكل أكثر إيجازًا، فقد حدث ذلك None في المثال الأول، الصف الثاني، العمود الثاني.هناك من الممكن بالفعل أن يكون لديك S, ، ولكن بما أن المنطق في CYK لا يمكنه إجراء المزيد من التحسينات مثل NP->NN.من هناك S -> NP VP للمذكور None تختفي الخلية.وبسبب عدم قدرة CYK على القيام بذلك، يجب أن تكون القواعد في CNF.لذا، يبدو الأمر تقريبًا كما لو كنت تحاول تطبيق مترجم C على برنامج C++ (بدون مكتبات C++).وحصلت محظوظ حتى للحصول على النتيجة الصحيحة في الأعلى.

ومع ذلك، لن أخوض في المثال الثاني لك.

فقط للتوضيح، هناك قواعد نحوية CNF إذا كان له قواعد فقط من هذين الشكلين:

س -> أ ب
أ-> أ

من الواضح أن شيئا من هذا القبيل NP -> NN ليس في CNF.