  Given a context free language $L(G)$ over alphabet $\Sigma$ and a string $s
\in \Sigma^*$, the language edit distance (Lan-ED) problem seeks the minimum
number of edits (insertions, deletions and substitutions) required to convert
$s$ into a valid member of $L(G)$. The well-known dynamic programming algorithm
solves this problem in $O(n^3)$ time (ignoring grammar size) where $n$ is the
string length [Aho, Peterson 1972, Myers 1985]. Despite its vast number of
applications, there is no algorithm known till date that computes or
approximates Lan-ED in true sub-cubic time.
  In this paper we give the first such algorithm that computes Lan-ED almost
optimally. For any arbitrary $\epsilon > 0$, our algorithm runs in
$\tilde{O}(\frac{n^{\omega}}{poly(\epsilon)})$ time and returns an estimate
within a multiplicative approximation factor of $(1+\epsilon)$, where $\omega$
is the exponent of ordinary matrix multiplication of $n$ dimensional square
matrices. It also computes the edit script. Further, for all substrings of $s$,
we can estimate their Lan-ED within $(1\pm \epsilon)$ factor in
$\tilde{O}(\frac{n^{\omega}}{poly(\epsilon)})$ time with high probability. We
also design the very first sub-cubic ($\tilde{O}(n^\omega)$) algorithm to
handle arbitrary stochastic context free grammar (SCFG) parsing. SCFGs lie at
the foundation of statistical natural language processing, they generalize
hidden Markov models, and have found widespread applications.
  To complement our upper bound result, we show that exact computation of SCFG
parsing, or Lan-ED with insertion as only edit operation in true sub-cubic time
will imply a truly sub-cubic algorithm for all-pairs shortest paths, and hence
to a large range of problems in graphs and matrices. Known lower bound results
on parsing implies no improvement over our time bound of $O(n^\omega)$ is
possible for any nontrivial multiplicative approximation.
