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

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

• What is "$\mid$" supposed to mean? Is it a symbol of the input word? Or do you mean something like $\{ 0^x 1^y \mid 0^{x+y} \in L \}$? – dkaeae Jan 15 at 15:21
• Regarding showing a language is not context-free, you can always try this. – dkaeae Jan 15 at 15:22
• @dkaeae Worth checking the source in cases like that. The OP didn't know that you need to escape braces in LaTeX so wrote ${...|...}$ instead of $\{...|...\}$. – David Richerby Jan 15 at 17:01

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\}$$.

• thank you very much. you've helped me understand this concept with a short and concise answer – Joto Jan 15 at 15:34