The following CFG in Chomsky normal form generates strings of balanced parentheses: V V2 V2 |...

Transcribed Image Text:

The following CFG in Chomsky normal form generates strings of balanced parentheses: V₁ V2 V2 | V4V3 | V4V5 | € V2 → V2V2 | V4V3 | V4V5 V3 → V₂V5 V4 → ( V5 →) 1. Recall that CYK running on a grammar with r variables and an input string w of length n populates an nxn x r array such that P[l, s, i] is true if and only if variable R₁ derives w... Ws+-1, the input substring of length & starting at index s. For the grammar above and input w = (0) (0)), give a true false answer describing the contents of each of the following cells: P[1, 4, 5] = P[1,5, 3] = P[5, 2, 1] = P[9, 2, 3] = Hint: Note that you do not need to run the whole algorithm to infer the subproblem answers. 2. Draw the parse tree and corresponding leftmost derivation for (()()). Hint: The unambiguous derivation is 11 steps. The following CFG in Chomsky normal form generates strings of balanced parentheses: V₁ V2 V2 | V4V3 | V4V5 | € V2 → V2V2 | V4V3 | V4V5 V3 → V₂V5 V4 → ( V5 →) 1. Recall that CYK running on a grammar with r variables and an input string w of length n populates an nxn x r array such that P[l, s, i] is true if and only if variable R₁ derives w... Ws+-1, the input substring of length & starting at index s. For the grammar above and input w = (0) (0)), give a true false answer describing the contents of each of the following cells: P[1, 4, 5] = P[1,5, 3] = P[5, 2, 1] = P[9, 2, 3] = Hint: Note that you do not need to run the whole algorithm to infer the subproblem answers. 2. Draw the parse tree and corresponding leftmost derivation for (()()). Hint: The unambiguous derivation is 11 steps.

Answer rating: 100% (QA)

b parse tree 3 Vy www 3 for V V V Vu V3 V3 V V5 V ... View the full answer