3
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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