If A and B are languages, define A⋄B={xy | x ∈ A and y ∈ B and |x|=|y|}. For example, if A = {00, 101, 111} and B= {1, 11, 00110}, we would have A⋄B={0011}.
Show that if A and B are regular, then A⋄B is a context-free language. (Hint: it might be helpful to think about NFAs and PDAs.)
The answer that I wrote was:
If A and B are regular, they can be represented by a NFA. Suppose A and B are both languages that accept the string of length 2.
I then drew two NFA's that accepted lengths of 2, and said the contatenation can easily be performed:
Followed by a drawing of the concatenation of A and B I wrote, this proves that A⋄B is a regular language. Since it can be represented as an NFA. Because a PDA is essentially an NFA with a stack, A⋄B can be represented by using a PDA with the stack omitted. Thus A⋄B is a context free language.
My answer was marked incorrect, my professor wrote A⋄B is not regular in genral. Take A=0* and B=1*. and A⋄B={0n1n } n >= 0}
I think the correct answer would have been to describe a PDA that takes in the input of A and pushes a symbol onto the stack for every input, nondeterministically runs input B after A is finished and pops the symbol for every input of B. Only accepting if it has reached the bottom of the stack when B is completed. I guess the example and hint he provided kind of threw me off, but I thought my answer deserved partial credit.
Best Answer
Here is a solution using some closure properties of context-free languages. Let $A$ and $B$ be regular languages of $\Sigma^*$. Let $\overline{\Sigma}$ be a disjoint copy of $\Sigma$ and let $\pi: (\Sigma \cup \overline{\Sigma})^* \to \Sigma^*$ be the monoid morphism defined by $\pi(x) = \pi(\overline{x}) = x$ for all $x \in \Sigma$. Let $\overline{B}$ be the copy of $B$ in $\overline{\Sigma}^*$ and let $L$ be the language of $(\Sigma \cup \overline{\Sigma})^*$ defined by $$ L = \{\ u\overline{v} \mid u \in \Sigma^*, v \in \overline{\Sigma}^* \text{ and } |u| = |v| \ \} $$ Then by construction $$ A \cdot B = \pi(A\overline{B} \cap L) $$ Let us show that $A \cdot B$ is context-free. Since $A\overline{B}$ is regular, it suffices to prove that $L$ is context-free (since context-free languages are closed under intersection with regular languages and under morphisms). This can be done directly or by observing that $L = \sigma(S)$ where $S$ is the context-free language $\{0^n1^n \mid n \geqslant 0\}$ and $\sigma$ is the finite substitution from $\{ 0, 1 \}^*$ to $(\Sigma \cup \overline{\Sigma})^*$ defined by $\sigma(0) = \Sigma$ and $\sigma(1) = \overline{\Sigma}$. Since context-free languages are closed under finite substitutions, $L$ is context-free.