خوارزمية CYK
خوارزمية كوك-يونغير-كاسامي Cocke-Younger-Kasami (وتسمى أيضاً CKY) هي خوارزمية تحليل نحوي تنتمي للقواعد النحوية الخالية من السياق في علوم الحاسوب، وقد سميت باسم مخترعيها، جون كوك، دانيال يونغير وتاداو كسامي. وهي تستخدم في التحليل من الأسفل إلى الأعلى والبرمجة الديناميكية.

يعمل الإصدار القياسي من الخوارزمية فقط على القواعد الخالية من السياق في نموذج تشومسكي الطبيعي (CNF). ومع ذلك، يمكن تحويل أي قواعد نحوية خالية من السياق إلى قواعد CNF معبرة عن نفس اللغة .

تنبع أهمية خوارزمية (CYK) من كفاءتها العالية في مواقف معينة. إذا ما قيمنا كفاءة عملها بواسطة مقياس التعقيد الحسابي Big O، فإن اسوء حالة تشغيل يمكن الحصول عليها في خوارزمية CYK هي ، حيث تمثل n طول الجملة المراد تحليلها فيما تمثل G حجم القواعد ضمن نموذج تشومسكي الطبيعي الذي يتم العمل عليه . ويجعلها هذا إحدى أكثر خوارزميات التحليل النحوي فاعلية، من ناحية التعقيد الحسابي.

النموذج الطبيعي 
تتطلب خوارزميات البرمجة الديناميكية تحويل القواعد النحوية الخالية من السياق إلى نموذج تشومسكي الطبيعي (CNF)، لأنها تختبر إمكانيات تجزئة التسلسل الحالي من البيانات إلى النصف يمكن تمثيل أي قواعد نحوية خالية من السياق لا تنشئ سلسلة فارغة في النموذج الطبيعي لتشومسكي وباستخدام قواعد إنتاج النماذج فقط (القواعد المتعلقة بتجزئة الرموز غير الطرفية إلى رموز طرفية) و .

الخوارزمية 

</div>تراعي هذه الخوارزمية كل جزء ممكن من الجمل ممكن من الجمل والمجموعات المدخلة  ليكون الجزء صحيحا إذا كانت بطول  بدءاً من وقابل للتوليد من العنصر غير الطرفي . عند أخذ جملة جزئية بطول (1)، تتجه الخوارزمية نحو الجمل الجزئية بطول (2)، وهكذا. لكل جملة جزئية بطول (2) أو أكثر، تأخذ الخوارزمية كل جزء معتبرة أنه يتكون من جزئين، ثم تقوم بفحص امكانية تطبيق إنتاج معين (قاعدة) بحيث أن Q تطابق الجزء الأول، وR تطابق الجزء الثاني، ثم تسجل P على أنها تطابق الجملة الجزئية كلياً. حالما تنتهي العملية، تميز الجملة من خلال القواعد إذا ما كانت الجملة الجزئية التي تتضمن جميع جمل المدخلات تنطبق على القاعدة الأساسية المبتدئة برمز البداية (S غالباً).

مثال 

يتم الآن تحليل الجملة (She eats a fish with a fork) «هي تأكل السمكة بالشوكة» باستخدام خوارزمية CYK. في الجدول أدناه، في  حيث i هو رقم الصف (يبدأ من أسفل في 1)، و  هو رقم العمود (يبدأ من اليسار في 1).

توضيح: VP جملة فعلية

NP جملة اسمية

PP جار ومجرور

DET أدوات التعريف والتنكير

N اسم

V فعل

S رمز البداية ورمز القاعدة ككل

توزيع الخوارزميات
خوارزمية كوك - يونغير - كاسامي Cocke - Younger - Kasami ( وتسمى أيضاً CKY ) هي خوارزمية تحليل نحوي تنتمي ل القواعد النحوية الخالية من السياق في علوم الحاسوب ، و قد سميت ب اسم مخترعي ها ، جون كوك ، دانيال يونغير وتاداو كسامي . و هي تستخدم في ال تحليل من الأسفل إلى الأعلى والبرمجة الديناميكية . يعمل ال إصدار القياسي من الخوارزمية فقط على القواعد الخالية من السياق في نموذج تشومسكي الطبيعي ( CNF ) . و مع ذلك ، يمكن تحويل أي قواعد نحوية خالية من السياق إلى قواعد CNF معبرة عن نفس اللغة \ . تنبع أهمية خوارزمية ( CYK ) من كفاءة ها العالية في مواقف معينة . إذا ما قيمنا كفاءة عمل ها ب واسطة مقياس التعقيد الحسابي Big O ، ف إن اسوء حالة تشغيل يمكن الحصول علي ها في خوارزمية CYK هي ، حيث تمثل n طول الجملة المراد تحليل ها فيما تمثل G حجم القواعد ضمن نموذج تشومسكي الطبيعي الذي يتم العمل علي ه \ . ويجعل ها هذا إحدى أكثر خوارزميات ال تحليل النحوي فاعلية ، من ناحية التعقيد الحسابي . النموذج الطبيعي تتطلب خوارزميات البرمجة الديناميكية تحويل القواعد النحوية الخالية من السياق إلى نموذج تشومسكي الطبيعي ( CNF ) ، لأن ها تختبر إمكانيات تجزئة التسلسل الحالي من البيانات إلى النصف يمكن تمثيل أي قواعد نحوية خالية من السياق لا تنشئ سلسلة فارغة في النموذج الطبيعي لتشومسكي وباستخدام قواعد إنتاج النماذج فقط ( القواعد المتعلقة بتجزئة الرموز غير الطرفية إلى رموز طرفية ) و \ . الخوارزمية < / div > تراعي هذه الخوارزمية كل جزء ممكن من الجمل ممكن من الجمل و المجموعات المدخلة ل يكون الجزء صحيحا إذا كانت ب طول بدءاً من وقابل للتوليد من العنصر غير ال طرفي \ . عند أخذ جملة جزئية ب طول تتجه الخوارزمية نحو الجمل الجزئية ب طول وهكذا . ل كل جملة جزئية بطولأو أكثر ، تأخذ الخوارزمية كل جزء معتبرة أن ه يتكون من جزئين ، ثم تقوم ب فحص امكانية تطبيق إنتاج معين ( قاعدة ) ب حيث أن Q تطابق الجزء الأول ، و R تطابق الجزء الثاني ، ثم تسجل P على أن ها تطابق الجملة الجزئية كلياً . حالما تنتهي العملية ، تميز الجملة من خلال القواعد إذا ما كانت الجملة الجزئية التي تتضمن جميع جمل المدخلات تنطبق على القاعدة الأساسية المبتدئة برمز البداية ( S غالباً ) . مثال يتم الآن تحليل الجملة ( She eats a fish with a fork ) « هي تأكل السمكة بالشوكة » ب استخدام خوارزمية CYK . في الجدول أدنا ه ، في حيث i هو رقم الصف ( يبدأ من أسفل في و هو رقم العمود ( يبدأ من اليسار في توضيح : VP جملة فعلية NP جملة اسمية PP جار ومجرور DET أدوات التعريف والتنكير N اسم V فعل S رمز البداية ورمز القاعدة ك كل توزيع الخوارزميات