Answer Happy

(8 points) Exercise 4 Context-free languages and the CYK algorithm (a) Consider the following grammar ({S, T, U}, {a,b,c), P, S) where P is defined as follows: S→ TbU TabT | E U → Ubc | E Transform this grammar into an equivalent grammar in Chomsky normal form. Write down the intermediate steps. (b) Consider the following grammar G = ({S, A, B}, {a, b, c), P, S), where P is defined as follows: S→ SA | a A → BA a B→BB|BS|b|c This grammar is already in Chomsky normal form. Use the CYK algorithm on this grammar to decide whether the word w = abbca is generated by the grammar. For this, write down the complete table of the algorithm, and briefly explain how, using the table, you can find out whether the word is generated by the grammar or not. (c) Let G be a grammar in Chomsky normal form. Explain why the runtime of the CYK-Algorithm for G is cubic in the size of its input. That means for a word w of length n the algorithm terminates after O(n³) steps. (Note: For this, consider the size of the table that has to be filled by the algorithm and the maximal number of steps needed to fill one of its cells.)