Describe a dynamic programming algorithm that takes as input a PCFG, a sentence, x, and an unlabeled phrase-structure tree (denoted by a collection of spans ((i1,ji), (i2, j2), ...,)), and produces the PCFG's most probable labeled tree consistent with the input. To simplify the problem a bit, assume that the PCFG is in Chomsky normal form and that every word's parent in the tree has a single child (i.e., that word), and that every other node of the tree has two children. The runtime of your algorithm should be linear in the size of the tree, and hence in the size of the sentence. Describe a dynamic programming algorithm that takes as input a PCFG, a sentence, x, and an unlabeled phrase-structure tree (denoted by a collection of spans ((i1,ji), (i2, j2), ...,)), and produces the PCFG's most probable labeled tree consistent with the input. To simplify the problem a bit, assume that the PCFG is in Chomsky normal form and that every word's parent in the tree has a single child (i.e., that word), and that every other node of the tree has two children. The runtime of your algorithm should be linear in the size of the tree, and hence in the size of the sentence