A string $y$ is said to be a permutation of the string $x$ if the symbols of $y$ can be reordered to make $x.$ For instance, the permutations of string $x=011$ are $110,101,$ and $011.$ If $L$ is a language then $\text{perm(L)}$ is the set of strings that are permutations of strings in $L.$ For example, if $L=\{0^{n}1^{n}|n\geq 1\},$ then $\text{perm(L)}$ is the set of strings with equal numbers of $0's$ and $1's.$
- Give an example of a regular language $L$ over alphabet $\{0,1\}$ such that $\text{perm(L)}$ is not regular.Justify your answer. Hint$:$ Try to fi nd a regular language whose permutations are all strings with an equal number of $0's$ and $1's.$
- Give an example of a regular language $L$ over alphabet $\{0,1,2\}$ such that $\text{perm(L)}$ is not context-free.
- Prove that for every regular language $L$ over a two-symbol alphabet , $\text{perm(L)}$ is context-free.