A grammar G is a way of generating strings of “terminal” characters from a nonterminal symbol S, by applying simple substitution rules, called productions. If B → β is a production, then we can convert a string of the form αBγ into the string αβγ. A grammar is in Chomsky normal form if every production is of the form “A → BC” or “A → a,” where A, B, and C are nonterminal characters and a is a terminal character. Design an O(n3)-time dynamic programming algorithm for determining if string x = x0x1 ··· xn−1 can be generated from the start symbol S.