خوارزمية CYK

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

تراعي هذه الخوارزمية كل جزء ممكن من الجمل ممكن من الجمل والمجموعات المدخلة ${\displaystyle P[l,s,v]}$ ليكون الجزء صحيحا إذا كانت بطول ${\displaystyle l}$ بدءاً من ${\displaystyle s}$وقابل للتوليد من العنصر غير الطرفي ${\displaystyle R_{v}}$. عند أخذ جملة جزئية بطول (1)، تتجه الخوارزمية نحو الجمل الجزئية بطول (2)، وهكذا. لكل جملة جزئية بطول (2) أو أكثر، تأخذ الخوارزمية كل جزء معتبرة أنه يتكون من جزئين، ثم تقوم بفحص امكانية تطبيق انتاج معين (قاعدة) ${\displaystyle P\to Q\;R}$بحيث أن Q تطابق الجزء الأول، وR تطابق الجزء الثاني، ثم تسجل P على أنها تطابق الجملة الجزئية كلياً. حالما تنتهي العملية، تميز الجملة من خلال القواعد إذا ما كانت الجملة الجزئية التي تتضمن جميع جمل المدخلات تنطبق على القاعدة الأساسية المبتدئة برمز البداية (S غالباً).

تحليل الجملة باستخدام خوارزمية CYK

يتم الآن تحليل الجملة (She eats a fish with a fork) "هي تأكل السمكة بالشوكة" باستخدام خوارزمية CYK. في الجدول أدناه، في ${\displaystyle P[i,j,k]}$ حيث i هو رقم الصف (يبدأ من أسفل في 1) ، و j هو رقم العمود (يبدأ من اليسار في 1).

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

NP جملة اسمية

PP جار ومجرور

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

N اسم

V فعل

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

• Cocke, John; Schwartz, Jacob T. (April 1970). Programming languages and their compilers: Preliminary notes (PDF) (Technical report) (الطبعة 2nd revised). معهد كورانت لعلوم الرياضيات, NYU. الوسيط |CitationClass= تم تجاهله (مساعدة)
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link) Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link) Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
• كاسامي، ت. (1965). خوارزمية فعالة للتعرف على تحليل وبناء الجملة للغات الخالية من السياق (تقرير فني). AFCRL . 65-758.
• Knuth, Donald E. (November 14, 1997). فن برمجة الحاسوب Volume 2: Seminumerical Algorithms (الطبعة 3rd). Addison-Wesley Professional. صفحة 501. ISBN 0-201-89684-2. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link) Knuth, Donald E. (November 14, 1997). فن برمجة الحاسوب Volume 2: Seminumerical Algorithms (الطبعة 3rd). Addison-Wesley Professional. صفحة 501. ISBN 0-201-89684-2. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link) Knuth, Donald E. (November 14, 1997). فن برمجة الحاسوب Volume 2: Seminumerical Algorithms (الطبعة 3rd). Addison-Wesley Professional. صفحة 501. ISBN 0-201-89684-2. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
• Lang, Bernard (1994). "Recognition can be harder than parsing". Comput. Intell. 10 (4): 486–494. doi:10.1111/j.1467-8640.1994.tb00011.x. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
• Lange, Martin; Leiß, Hans (2009). "To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm". Informatica Didactica. 8. مؤرشف من الأصل في 18 ديسمبر 2019. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
• Lee, Lillian (2002). "Fast context-free grammar parsing requires fast Boolean matrix multiplication". J. ACM. 49 (1): 1–15. arXiv:cs/0112018. doi:10.1145/505241.505242. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
• Sipser, Michael (1997). Introduction to the Theory of Computation (الطبعة 1st). IPS. صفحة 99. ISBN 0-534-94728-X. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link) Sipser, Michael (1997). Introduction to the Theory of Computation (الطبعة 1st). IPS. صفحة 99. ISBN 0-534-94728-X. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link) Sipser, Michael (1997). Introduction to the Theory of Computation (الطبعة 1st). IPS. صفحة 99. ISBN 0-534-94728-X. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
• Valiant, Leslie G. (1975). "General context-free recognition in less than cubic time". J. Comput. Syst. Sci. 10 (2): 308–314. doi:10.1016/s0022-0000(75)80046-8. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
• Younger, Daniel H. (February 1967). "Recognition and parsing of context-free languages in time n³". Inform. Control. 10 (2): 189–208. doi:10.1016/s0019-9958(67)80007-x. الوسيط |CitationClass= تم تجاهله (مساعدة)

• بوابة علم الحاسوب