Sign up ×

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.

share|cite|improve this question
Did the question really say that $A\diamond B=\{0011\}$? Because in fact $A\diamond B=\{0011,101111,111111\}$. – Brian M. Scott Jun 6 '13 at 7:32
It was a typo, sorry. – user2357373 Jun 6 '13 at 7:35
I agree with your thoughts about the way sketched in your last paragraph (after all, it makes use of the original hint). If your final statement shoul dbe what yuo really want to ask, I don't know: You think you prove something much stronger than requested (though you add a very striog additional constraint about the accepted string lengths) and that should have given you suspicions ... – Hagen von Eitzen Jun 6 '13 at 8:06
I see your professor's perspective on this. The essential element of the solution is using the stack to handle arbitrary lengths (depending on $A$, of course), which you sidestepped by fixing the length. (Your answer is, of course, correct, the challenge is detecting bottom of stack.) – copper.hat Jun 6 '13 at 18:46

1 Answer 1

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.

share|cite|improve this answer

Your Answer


