4. (5 pts) Let skip(I) = fuw | u, U, w E E* and ww E I}. Prove by construction on grammars
that skip is closed over context-free languages.
Note: it can be helpful to assume that the grammar for language L is in Chomsky Normal
Form (CNF). For a grammar GL = (V, 2, R, $) in CNF, all production rules are of the form
A -> BC or A -> o (for A E V and B, C € VIS} and o EX), except that there may be one rule S – e to allow for languages with the empty string. In other words, you can assume that all production rule righthand sides are either exactly two nonterminals or exactly one terminal. The textbook contains a proof that any context-free grammar can be converted to an equivalent grammar in CNF. This assumption isn’t critical to solve this problem, but it may make your proof simpler. Your constructed grammar does not need to be in CNF.