patternModerate
Cases where string concatenation is commutative
Viewed 0 times
wherecommutativeconcatenationstringcases
Problem
Strings are known to not satisfy the commutative property.
pq is not equal qp unless p is empty string. Is there a case where pq can be qp where both are non empty strings and p and q are distinct
pq is not equal qp unless p is empty string. Is there a case where pq can be qp where both are non empty strings and p and q are distinct
Solution
Simple solution: $a\cdot aa = aa \cdot a$?
In general there is a characterization due to Lyndon and Schützenberger.
For nonempty words $x,y\in \Sigma^+$ the following are equivalent:
This means that $x$ and $y$ commute ($xy=yx$) iff they are powers of the same string, like $bbabba\cdot bbabbabba = bbabbabba \cdot bbabba$. So, basically the examples will not get more complicated than the proposal $a\cdot aa = aa \cdot a$ above.
In general there is a characterization due to Lyndon and Schützenberger.
For nonempty words $x,y\in \Sigma^+$ the following are equivalent:
- $xy=yx$
- there exists $z\in \Sigma^+$ such that $x=z^k$ and $y=z^\ell$ for some $k,\ell >0$.
- there exist $i,j>0$ such that $x^i = y^j$.
This means that $x$ and $y$ commute ($xy=yx$) iff they are powers of the same string, like $bbabba\cdot bbabbabba = bbabbabba \cdot bbabba$. So, basically the examples will not get more complicated than the proposal $a\cdot aa = aa \cdot a$ above.
Context
StackExchange Computer Science Q#80733, answer score: 12
Revisions (0)
No revisions yet.