= Solution
This language is \b[not context-free]. Suppose it were, and define the homomorphism
$$
h(a)=h(c)=a,qquad h(b)=h(d)=b.
$$
Then closure under inverse homomorphism and <intersection of a context-free language with a regular language> would make
$$
h^{-1}(L)cap a^+b^+c^+d^+
={a^m b^n c^m d^n:m,ngeq1}
$$
context-free. The equality holds because the midpoint of a square with four nonempty alternating runs must lie between its second and third runs.
Apply the <pumping lemma for context-free languages> to $a^pb^pc^pd^p$. A pumpable window of length at most $p$ meets at most two adjacent blocks. Pumping changes at least one block but cannot reach its equal-count partner two blocks away, so either the $a,c$ counts or the $b,d$ counts cease to agree. This contradiction proves the claim.
Back to article page
