is $0^x1^y$ context-free?

Question

given that L is regular, does the following make a context-free language?:

i) $\{0^x1^y \mid 0^{x+y} \in L\}$

ii) $\{0^x1^y \mid 0^{x-y} \in L\}$

since L is regular, i presumed that i) can be put into a pushdown automata, but i don't see how to do that for ii). if ii) cannot be put into a pushdown automata, it means it is neither context free nor regular? how can it be shown?

and regarding i) it is a context free, right?

thank you very much for your effort. first post here and i'm glad to join this community

Answer 1

Your first language is actually regular: if $s$ is the substitution mapping $0$ to $\{0,1\}$, then $$ \{ 0^x 1^y : 0^{x+y} \in L \} = s(L \cap 0^*) \cap 0^*1^*. $$ Your second language is context-free, since we can write it as $L \cap 0^*$ concatenated with $\{0^y 1^y : y \geq 0\}$. It need not be regular, as the example of $L = \{\epsilon\}$ demonstrates: in this case, your language is just $\{0^y1^y : y \geq 0\}$.