0
$\begingroup$

Prove that the unique language $A\subseteq \Sigma^*$ such that $AB$ is context free for all languages $\subseteq \Sigma^*$ is the empty set.

If $A$ is not the empty set, there should be a way to construct a language $B$ so that $AB$ is not context-free. I'm not sure how to generalize this for arbitrary nonempty languages $A$ however. The language $\{0^n 1^n 0^n : n\in\mathbb{N}\}$ is known to be non-context-free. Also, removing finitely many strings from a non-context-free language results in a non-context free language.

Edit: perhaps modifying the language given will work.

$\endgroup$

1 Answer 1

1
$\begingroup$

If $AB$ is context-free, so should be the set of all its suffixes. Those include the suffixes of $B$, and if $B$ is complicated enough prefixing $A$ does not change the complexity of the set of suffixes.

Your solution $B = \{0^n1^n0^n \mid \dots \}$ seems to work, but if $A$ ends in $0^*$ the reasoning becomes a little complicated. I would suggest $B' = \{10^n1^n0^n \mid \dots \}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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