The following CFG is in Chomsky normal form. The table below is a partially filled CYK...

Transcribed Image Text:

The following CFG is in Chomsky normal form. The table below is a partially filled CYK table for determining if the string aabbcc is in the language of this grammar. 1 10 La 5 C 1 A 2 S→ AY | AC | BX | b | e W → AY | AC | BX | b X→ BX | b Y → WC A → a B → b C → c 02 a A 3 aab ab 0 b S,W,B,X 4 Gabb abb bb d S,W,B,X 5 aabbe aaba be C C 6 aabbee abboc boce boo 8 C Which variable(s) should go in table entry (3,4) for the substring bb? Select all that apply. S OC W Y X B Question 2 (2 points) Answer the same question as above for the table entry (4,5) for the substring bc. Select all that apply. B W S nx The following CFG is in Chomsky normal form. The table below is a partially filled CYK table for determining if the string aabbcc is in the language of this grammar. 1 10 La 5 C 1 A 2 S→ AY | AC | BX | b | e W → AY | AC | BX | b X→ BX | b Y → WC A → a B → b C → c 02 a A 3 aab ab 0 b S,W,B,X 4 Gabb abb bb d S,W,B,X 5 aabbe aaba be C C 6 aabbee abboc boce boo 8 C Which variable(s) should go in table entry (3,4) for the substring bb? Select all that apply. S OC W Y X B Question 2 (2 points) Answer the same question as above for the table entry (4,5) for the substring bc. Select all that apply. B W S nx