CS 475 Midterm: CS 475 Alabama Fall2017 Exam3 2
Document Summary
You may choose any set of problems that adds up to 100 or more points. Cs 475 recommended problems are 1, 2, 3. Cs 575 recommended problems are 3, 4, 5: complete the table for the cyk dynamic programming algorithm using input string abcdedcba and the cnf grammar shown below. Hint: notice the symmetry in both the grammar rules and the input string. [30 points for cs 475] [20 points for cs 575] 9: first indicate each subset of states that are equivalent, and then draw an equivalent dfsm with the minimum number of states. The start vertex is in the center (labelled s ). Example: if l1 = {a,d,e,g,k}, l2 = {b,d,f,h. k}, l3 = {c,e,f,j,k}, then majority(l1, l2, l3) = {d,e,f,k}: determine whether or not the regular languages are closed over the majority operation. [20 points: determine whether or not the context-free languages are closed over the majority operation. You must provide convincing justification for your answer.
