<p>Your idea only works on languages with finite descriptions; here is an approach that's well defined for all languages, but it requires choosing some probability distribution <span class="math-container">$\mu$</span> on the set of all finite words, <span class="math-container">$\Sigma^*$</span>. Assuming that you've chosen one, let <span class="math-container">$A$</span> and <span class="math-container">$B$</span> be your two languages. Let <span class="math-container">$X$</span> be the random variable corresponding to the event that a <span class="math-container">$\mu$</span>-random word belongs to <span class="math-container">$A$</span>, and define <span class="math-container">$Y$</span> analogously for <span class="math-container">$B$</span>. Now you can define correlation between <span class="math-container">$A$</span> and <span class="math-container">$B$</span> as the correlation between <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> in the classical sense:
<span class="math-container">$$ cov(X,Y) = E[XY]-E[X]E[Y] = 
\sum_{x\in\Sigma^*}1[x\in A\cap B]\mu(x)
-
\sum_{x,y\in\Sigma^*}1[x\in A]1[y\in B]\mu(x)\mu(y)
,
$$</span>
and <span class="math-container">$cor(X,Y)=\frac{cov(X,Y)}{\sigma_X\sigma_Y}$</span>, where
<span class="math-container">$$
\sigma_X^2 = \sum_{x\in\Sigma^*}1[x\in A]\mu(x)
-
\left(
\sum_{x\in\Sigma^*}1[x\in A]\mu(x)
\right)^2.
$$</span></p>
<p>A reasonable choice of <span class="math-container">$\mu$</span> would be to let word length be distributed, say, geometrically (or any other distribution on the integers), and within each fixed word length, <span class="math-container">$\mu$</span> is uniform. But of course the &quot;reasonableness&quot; or usefulness of this definition will depend entirely on your purposes.</p>

CC BY-SA 4.0
2020-11-28T15:38:54.693Z
2020-11-28T17:49:45.197Z
2020-11-28T17:49:45.197Z
Aryeh
<p>How does one define the concept of correlation between languages?</p>
<p>Is there any 'standard' measure of 'correlation' between two (possibly inf) sets of strings / an analogue of the concept in this setting?</p>
<p>Was thinking could use the algorithmic mutual information between their descriptions--maybe this works for languages with finite descriptions?</p>

CC BY-SA 4.0
2020-11-28T15:39:44.180Z
Various reasonable definitions are possible; I suggested one such in my answer. What is your ultimate motivation in asking this?
Aryeh
<fl.formal-languages><kolmogorov-complexity>
how to define "correlation" between languages?
DeeDee
# how to define "correlation" between languages?

(Asked by: username_0 on 2020-11-27)

How does one define the concept of correlation between languages?

Is there any 'standard' measure of 'correlation' between two (possibly inf) sets of strings / an analogue of the concept in this setting?

Was thinking could use the algorithmic mutual information between their descriptions--maybe this works for languages with finite descriptions?

**Tags:** fl.formal-languages, kolmogorov-complexity

> **Comments:**
> **username_1**: Various reasonable definitions are possible; I suggested one such in my answer. What is your ultimate motivation in asking this?  

---

## 1 answers

### Answer by username_1 on 2020-11-28. Score: 2 | Accepted answer

Your idea only works on languages with finite descriptions; here is an approach that's well defined for all languages, but it requires choosing some probability distribution $\mu$ on the set of all finite words, $\Sigma^\*$. Assuming that you've chosen one, let $A$ and $B$ be your two languages. Let $X$ be the random variable corresponding to the event that a $\mu$-random word belongs to $A$, and define $Y$ analogously for $B$. Now you can define correlation between $A$ and $B$ as the correlation between $X$ and $Y$ in the classical sense:
$$ cov(X,Y) = E[XY]-E[X]E[Y] =
\sum\_{x\in\Sigma^\*}1[x\in A\cap B]\mu(x)
-
\sum\_{x,y\in\Sigma^\*}1[x\in A]1[y\in B]\mu(x)\mu(y)
,
$$
and $cor(X,Y)=\frac{cov(X,Y)}{\sigma\_X\sigma\_Y}$, where
$$
\sigma\_X^2 = \sum\_{x\in\Sigma^\*}1[x\in A]\mu(x)
-
\left(
\sum\_{x\in\Sigma^\*}1[x\in A]\mu(x)
\right)^2.
$$

A reasonable choice of $\mu$ would be to let word length be distributed, say, geometrically (or any other distribution on the integers), and within each fixed word length, $\mu$ is uniform. But of course the "reasonableness" or usefulness of this definition will depend entirely on your purposes.


---

