  Probabilistic context-free grammars (PCFGs) are used to define distributions
over strings, and are powerful modelling tools in a number of areas, including
natural language processing, software engineering, model checking,
bio-informatics, and pattern recognition. A common important question is that
of comparing the distributions generated or modelled by these grammars: this is
done through checking language equivalence and computing distances. Two PCFGs
are language equivalent if every string has identical probability with both
grammars. This also means that the distance (whichever norm is used) is null.
It is known that the language equivalence problem is interreducible with that
of multiple ambiguity for context-free grammars, a long-standing open question.
In this work, we prove that computing distances corresponds to solving
undecidable questions: this is the case for the L1, L2 norm, the variation
distance and the Kullback-Leibler divergence. Two more results are less
negative: 1. The most probable string can be computed, and, 2. The Chebyshev
distance (where the distance between two distributions is the maximum
difference of probabilities over all strings) is interreducible with the
language equivalence problem.
