Let $A = \{a,b\}$ be an alphabet.

Define a binary operation $\diamond: A^* \times A^* \rightarrow A^*$, which is commutative but not associative. Prove that your operation has the two properties.

My answer: I wanted to create an operation which compares two letters at the same index. If they are the same letters it will become $a$. And if they are different letters it will become $b$. If $|w_1| \neq |w_2|$ empty words would be used.

$\forall i \in \mathbb{N}$ $\forall w_1(i), w_2(i) \in A^*:\\ w_1(i) \diamond w_2(i) = \begin{cases} a, \text{if they are the same letters at i} \\ b, \text{if they are different letters at i}\end{cases}$

So I'm not quite sure how to define that.

For the prove wouldn't I have to take two random words out of $A^*$ and compare them:

Let $w_1(i), w_2(i) \in A^*$.

If anyone has an easier solution, that would be quite helpful.

  • $\begingroup$ That looks like a perfectly sensible definition, though I would have written $w_1 \diamond w_2 (i) = ...$, because you want to mean the $i$th element of your newly created string $w_1 \diamond w_2$. Unfortunately, it's associative. (The trick to seeing this quickly is to note that either the three strings have different lengths, in which case the result must be the empty string, or they all have the same length, in which case you're giving the $n$-fold product of the same operation on the singletons.) ((Edited: I've just realised it's (mod 2) addition)) $\endgroup$ Nov 4 '19 at 12:37
  • 1
    $\begingroup$ Guess what operation this is: $$a*b = b*a = ab$$ $$aa*ab = ab*aa = aaab$$ $$aba*aa = aa*aba = aaaba$$ $$(abb*bab)*abab = abbbababab$$ $$abb*(bab*abab) = ababbababb$$ Hint: Observe that the words are intact. $\endgroup$
    – M. Vinay
    Nov 4 '19 at 13:14
  • $\begingroup$ @M.Vinay I don't get it $\endgroup$
    – franz3
    Nov 4 '19 at 17:16
  • $\begingroup$ @franz3 $$w_1 * w_2 = \operatorname{concat}(\operatorname{lexSort}(w_1, w_2))$$ $$w_1 * w_2 = \begin{cases} w_1w_2, & w_1 \le w_2\\ w_2w_1, & w_2 < w_1\end{cases}$$ where $\le$ stands for "precedes in lexicographical order". $\endgroup$
    – M. Vinay
    Nov 4 '19 at 17:45

Your definition of $\diamond$ is not clear. I suppose that $w(i)$ denotes the $i$-th letter of $w$. But then, you should define $w_1 \diamond w_2$ (and not $w_1(i) \diamond w_2(i)$ as you do). Moreover, whatever definition you take, you should prove that it is commutative, but not associative.

One possibility would be to define $u \diamond v = a^{||u|-|v||}$ where $||u|-|v||$ is the absolute value of the difference between the lengths of $u$ and $v$. It is clearly commutative, but it is not associative, since $(a \diamond (a^2 \diamond a^3) = a \diamond a = 1$ but $(a \diamond a^2) \diamond a^3 = a \diamond a^3 = a^2$.


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.