Automata and Complexity, Non Regular and Context Free Languages

$1.(8$ points$)$ Let $L$ be a regular language. Define $L^{}=\{xayin{}^{**}|xyinL,ain\}.$ We take the strings in $L,$ and add exactly one symbol anywhere in the string for anywhere it could be placed, even possibly at the beginning or end. Prove that if $L$ is regular, then so is $L^{\text{'}}.$

$2.(8$ points$)$ Prove that $\{0^m{1}^n|mn\}$ is not regular.

$3.(8$ points$)$ Give a CFG for valid regular expressions over the alphabet $=\{a,b\}.$ The alphabet of your grammar should be over $.$ You may insert more parenthesis than necessary. Here we shall use $$ to represent the base$-$case regular expression symbolizing the set only containing the empty string, that is$,=\{\}.$ Use the symbol $$ not as part of the regular expression, but if necessary, as part of the right$-$hand$-$side of productions of the grammar to satisfy $(V{)}^{**}.$ You must generate all syntactically valid regular expressions.