If $A$ and $B$ are languages over the same alphabet $\Sigma$, what can we say about $A$ and $B$ if $AB = BA$? Is there some way to characterize all languages with this property?


2 Answers 2


Let $\Sigma$ be a finite alphabet. Given regular languages $A,B \subseteq \Sigma^{\ast}$ we want to solve $AB = BA$, which means every word $uv \in AB$ with $u \in A, v \in B$ has a prefix in $B$ and a suffix in $A$, i.e. we have $uv = yx$ for $y \in B$ and $x \in A$.

Now I guess your are looking for necessary and sufficient criteria on $A$ and $B$ such that the equation $AB = BA$ holds. I can only give you partial answers.

i) First note that if $A,B$ form submonoids, i.e. we have $A^2 \subseteq A$ and $B^2 \subseteq B$ and both contain the empty word, then $$ AB = BA \Leftrightarrow (AB)^2 \subseteq AB $$ i.e. $AB$ forms itself a submonoid. For the proof note that if $AB = BA$ then $(AB)^2 = A^2B^2 \subseteq AB$, and conversely as $B \subseteq AB$ and $A \subseteq AB$ we have $BA \subseteq (AB)^2 \subseteq AB$, and for sets of words we have $BA \subseteq AB$ iff $BA = AB$ (I give a proof below).

ii) For the more general case lets try to use Levi's lemma and for language $U,V \subseteq \Sigma^{\ast}$ set $$ U^{-1}V := \{ w \in \Sigma \mid \exists u \in U : uw \in V \} \quad UV^{-1} := \{ w \in \Sigma \mid \exists v \in V : wv \in U \} $$ i.e. words that remain if we take away initial segments from $U$ or suffixes from $V$. Than Levi's lemma states that $$ uv = xy \Leftrightarrow ( \{u\}^{-1}\{x\} \cap \{v\}\{y\}^{-1} ) \cup ( \{x\}^{-1}\{u\} \cap \{ y\} \{v\}^{-1} ) \ne \emptyset. $$ So generalising we may set for $A,B \subseteq \Sigma^{\ast}$ $$ L := A^{-1}B \cap AB^{-1}. $$ Then we have that if $B \subseteq LA$ and $AL \subseteq A$ then $AB = BA$. For a proof suppose that $uv \in AB$ with $u \in A, v \in B$, and assume $v = wx$ with $x \in A, w \in L$. Then $uv = uwx$ and with $uw \in A$ we have $AB \subseteq BA$. Now this assumption is quite strong, and I do not think that a converse holds.

Note that I do not used regularity of $A$ and $B$, and I have no idea how to use it, beside maybe that $AB = BA$ is a decidable question then as we can construct automata for their concatenation and test if they accept the same language.

Appendix: For languages $A,B \subseteq \Sigma^{\ast}$ we have $AB \subseteq BA$ iff $AB = BA$. For each fixed $n$ in $AB$ and in $BA$ there are the same number of words of length $n$, as there is an easy bijection $uv \mapsto vu$ for $u\in A, v \in B$. So $AB \subset BA$ gives $AB \cap \Sigma^n \subseteq BA \cap \Sigma^n$ for each $n$, hence $AB \cap \Sigma^n = BA \cap \Sigma^n$. As these finite sets partition $AB$ and $BA$ the result follows.


Your question is related to famous problem formulated by Conway [1, p. 55 and 124] in 1971. Given a regular language $L$, is the largest language commuting with $L$ also regular?

However, in a famous breakthrough paper, Kunc [3] gave the most negative possible answer to Conway’s problem by showing that there exists a finite language $L$ such that the greatest solution of the equation $XL = LX$ is co-recursively enumerable complete.

This contrasts with the fact that the largest solution of the inequality $XK \subseteq LX$ is regular provided that the language $L$ is regular, as proved in [2].

[1] J. H. Conway, Regular Algebra and Finite Machines, Chapman and Hall, London, 1971.

[2] M. Kunc, Regular solutions of language inequalities and well quasi- orders. Theoret. Comput. Sci. 348(2–3) (2005) 277–293.

[3] M. Kunc, The power of commuting with finite sets of words, Theory Comput. Syst. 40,4 (2007), 521–551.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .