בשאלה זו שני חלקים: בחלק הראשון נפתור בעיית ספירה עם גנרטור, ובחלק השני נרחיב את אלגוריתם CYK.
סעיף א (12 נק'). ממשו את פונקציית הגנרטור asc_ind המקבלת כקלט שלושה מספרים שלמים i,j,k ונתון כי 0≤i<j וגם k≥2. הפונקציה תחזיר אובייקט מטיפוס גנרטור אשר מייצר את כל הרשימות באורך k בדיוק מהצורה [a1,a2,…,ak] המקיימות:
1. a1=i, ak=j.
2. לכל 1<r≤k מתקיים ar−1<ar.
3. לכל 1≤r≤k, ar הוא מספר שלם.
במילים: כל סדרות המספרים העולים ממש באורך k בדיוק שמתחילים ב-i ומסתיימים ב-j.
סעיף ב (13 נק'). בסעיף זה נעסוק בדקדוקים חסרי הקשר. כרגיל, נשתמש באותיות גדולות לייצוג משתנים, באותיות קטנות לייצוג טרמינלים וב-ϵ לייצוג המחרוזת הריקה.
נתון דקדוק t-CNF ודקדוק כלשהו, השלימו את הפונקציה new_cyk_env שמשמשת כפונקציית מעטפת ל-new_cyk_rec. הקלט: מחרוזת st, מילון rule_dict שכל כלל בו הוא ברצורת t-CNF, ומשתנה ההתחלה start_var. הפלט: True אם st בשפת הדקדוק ו-False אחרת. ניתן וצריך להשתמש בפונקציית הגנרטור asc_ind כפונקציה מעטפת.