how to define "correlation" between languages? 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?
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 &quot;reasonableness&quot; or usefulness of this definition will depend entirely on your purposes.