  The edit distance between two words $w_1, w_2$ is the minimal number of word
operations (letter insertions, deletions, and substitutions) necessary to
transform $w_1$ to $w_2$. The edit distance generalizes to languages
$\mathcal{L}_1, \mathcal{L}_2$, where the edit distance from $\mathcal{L}_1$ to
$\mathcal{L}_2$ is the minimal number $k$ such that for every word from
$\mathcal{L}_1$ there exists a word in $\mathcal{L}_2$ with edit distance at
most $k$. We study the edit distance computation problem between pushdown
automata and their subclasses. The problem of computing edit distance to a
pushdown automaton is undecidable, and in practice, the interesting question is
to compute the edit distance from a pushdown automaton (the implementation, a
standard model for programs with recursion) to a regular language (the
specification). In this work, we present a complete picture of decidability and
complexity for the following problems: (1)~deciding whether, for a given
threshold $k$, the edit distance from a pushdown automaton to a finite
automaton is at most $k$, and (2)~deciding whether the edit distance from a
pushdown automaton to a finite automaton is finite.
