Michael Sipser Edition 3 Exercise 2 Question 44 (Page No. 158)

Question

If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and}  \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a CFL.

Comments

Clearly there is a comparison between x and y , so its a cfl.

Answer 1

Suppose,  A = { 0^n | n > 0 }    and

                 B = { 1^n | n > 0 }

     By def. of a and b having  any no of 0s and 1s repectively

 both are regular languages

BUT,   A ∘ B = { 0^n.1^n  | n >0 }

         which is a renowned  cfl .

same applies for →  B∘A