Question: Apply CYK algorithm to check whether word 0 1 0 0 1 0 1 1 is generated by the following grammar or not. You need

Apply CYK algorithm to check whether word 01001011 is generated by the following grammar or not. You need to show the detail of constructing table as each rows are filled as we did with another example in the class. Fill in the corresponding row in each table. Show your work in detail for each step.
S AB | BA
A XC |0
B XD|1
C AX
D BX
X 0|1
Note: I understand up to Row 3, but Row 4 and above are what's confusing me.
I understand that a substring can be split (to have 2 and 2,1 and 3, & 3 and 1).
I may be incorrect but for Row 4 Column 1, I got C and S as the non-terminals.
Apply CYK algorithm to check whether word 0 1 0 0

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!