1
$\begingroup$

Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.

If $A$ is a language, then \begin{align*} AA^* & = A(A^0\cup A^1\cup\cdots) \tag{Definition of $A^*$}\\ & = A^1\cup A^2\cdots \tag{Distributive law} \\ & = (A^0\cup A^1\cup\cdots)A \tag{Distributive law} \\ & = A^*A. \end{align*}

Is this enough? I'm thinking that in order for it to be a proper proof, I have to show that $AA^*$ and $A^*A$ are subsets of each other. That is, take an element $s = xy$ where $x\in A$ and $y\in A^*$ and show that $x\in A^*$ and $y\in A$ (and vice versa). However, I get stuck very early when doing that method.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ The proof looks correct if you accept that left and right concatenations distribute over countable unions. $\endgroup$ – Steven Sep 29 '20 at 17:23
  • $\begingroup$ If $x\in AA^*$ then there are $a\in A$ and $b\in A^*$ such that $x=ab$. Since $b\in A^*$ then either there are $b_1,b_2,...,b_n\in A$, with $n\geq 1$, such that $b=\prod_{k\in[1,n]}b_k$ or $b=\epsilon$. It follows that either $x=a\prod_{k\in[1,n]}b_k$ or $x=a$. In the first case you can write $x=(a\prod_{k\in[1,n-1]}b_k)b_n$. Since $a\prod_{k\in[1,n-1]}b_k\in A^*$ and $b_n\in A$, you get that $x\in A^*A$. In the second case $x=a=\epsilon a$. Since $\epsilon\in A^*$ and $a\in A$, then we get again that $x\in A^*A$. So, $AA^*\subset A^*A$. The reverse inclusion is pretty much the same argument. $\endgroup$ – plop Sep 30 '20 at 13:49
  • $\begingroup$ @plop This to me appears very complete. I recommend you put it in an answer so I can accept it! $\endgroup$ – John Sep 30 '20 at 15:39
  • $\begingroup$ A language is commutative if any word obtained by permutating the letters of a word of the language is still in the language. Is this the definition you are referring to? $\endgroup$ – J.-E. Pin Oct 3 '20 at 10:06
  • $\begingroup$ @J.-E.Pin I was referring to the typical definition of commutativity, i.e., $x * y = y * x$ for some binary operation $*$. $\endgroup$ – John Oct 4 '20 at 15:52
1
$\begingroup$

If $x\in AA^∗$ then there are $a\in A$ and $b\in A^∗$ such that $x=ab$. Since $b\in A^∗$ then either there are $b_1,b_2,...,b_n\in A$, with $n\geq1$, such that $b=\prod_{k\in[1,n]}b_k$ or $b=\epsilon$. It follows that either $x=a\prod_{k\in[1,n]}b_k$ or $x=a$. In the first case you can write $x=\left(a\prod_{k\in[1,n−1]}b_k\right)b_n$, since concatenation is associative. Since $a\prod_{k\in[1,n−1]}b_k\in A^∗$ and $b_n\in A$, you get that $x\in A^∗A$. In the second case $x=a=\epsilon a$, since $\epsilon$ is a neutral under concatenation. Since $\epsilon\in A^∗$ and $a\in A$, then we get again that $x\in A^∗A$. So, $AA^∗\subset A^∗A$.

The reverse inclusion is pretty much the same argument, but starting with $x\in A^*A$.

Improve this answer
$\endgroup$
1
$\begingroup$

$AA^*$ is the set of all strings consisting of a string in A, followed by zero or more strings in A, which means all strings consisting of one or more strings in A. $A^*A$ is the set of all strings consisting of zero or more strings in A, followed by one string in A, which also means all strings consisting of one or more strings in A. So both are the same.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.