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

  • $\begingroup$ 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 \}$? $\endgroup$ – dkaeae Jan 15 at 15:21
  • $\begingroup$ Regarding showing a language is not context-free, you can always try this. $\endgroup$ – dkaeae Jan 15 at 15:22
  • 2
    $\begingroup$ @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 $\{...|...\}$. $\endgroup$ – 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\}$.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.