0
$\begingroup$

What is the mathematical notation or terms for the following relation between two strings

Given a pattern and a string str, find if str follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a letter in str.

Example : "aab" follows "bbd". My question is how to say this with formal mathematical notation?

$\endgroup$
0
$\begingroup$

I assume you're working with finite strings and a finite number of possible characters, so I'm giving my answer on this assumption, but I believe all that follows can be extended to at least countably long strings and countably many characters with no problem.

Let $X$ be the set of all finite strings, which consist of characters from the finite set $S$. Let $\mathcal{F}$ be the set of all bijections $f:S \to S$. Define a relation on $X$ such that for two strings of the same length $(x_1x_2\ldots x_n)$ and $(y_1,y_2\ldots y_n)$ we have $(x_1x_2\ldots x_n) \sim (y_1y_2\ldots y_n)$ if and only if $(x_1x_2\ldots x_n) = (f(x_1),f(x_2)\ldots f(x_n))$ for some $f \in \mathcal{F}$.

Now, as a shorthand I will denote the sequence $(x_1x_2\ldots x_n) \in X$ by $x$. And I will denote the sequence $(f(x_1)f(x_2)\ldots f(x_n) \in X$ by $f(x)$.

You can check that the relation defined above on $X$ is an equivalence relation. It is clearly reflexive, which you can see by letting $f$ be the identity. It is symmetric, because if $x = f(y)$ for some $f \in \mathcal{F}$ then we have that $y = f^{-1}(x)$ with $f^{-1}$ also in $\mathcal{F}$. Finally, it is transitive, because if $x=f(y)$ and $y = g(z)$ for some $f,g \in \mathcal{F}$ then we have $x = (f\circ g)(z)$ with $f\circ g \in \mathcal{F}$.

As a concrete example, take $S$ to be the set of letters in the English alphabet. Then $X$ is the set of all finite words created from these characters, and $\mathcal{F}$ is the set of all permutations, or rearrangements of these letters. Then $aab \in X$ and $bbd \in X$. Now, take any permutation in $\mathcal{F}$ which sends $a \to b$ and $b \to d$. Call this permutation $f$. By the definition of the equivalence relation above we have that $aab \sim bbd$ since $aab = f(a)f(a)f(b)$.

$\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.