  Let $G$ be a quasi-transitive, locally finite, connected graph rooted at a
vertex $o$, and let $c_n(o)$ be the number of self-avoiding walks of length $n$
on $G$ starting at $o$. We show that if $G$ has only thin ends, then the
generating function $F_{\mathrm{SAW},o}(z)=\sum_{n \geq 0} c_n(o) z^n$ is an
algebraic function. In particular, the connective constant of such a graph is
an algebraic number.
  If $G$ is deterministically edge labelled, that is, every (directed) edge
carries a label such that any two edges starting at the same vertex have
different labels, then the set of all words which can be read along the edges
of self-avoiding walks starting at $o$ forms a language denoted by
$L_{\mathrm{SAW},o}$. Assume that the group of label-preserving graph
automorphisms acts quasi-transitively. We show that $L_{\mathrm{SAW},o}$ is a
$k$-multiple context-free language if and only if the size of all ends of $G$
is at most $2k$. Applied to Cayley graphs of finitely generated groups this
says that $L_{\mathrm{SAW},o}$ is multiple context-free if and only if the
group is virtually free.
