  Let $X=(V\!X,E\!X)$ be an infinite, locally finite, connected graph without
loops or multiple edges. We consider the edges to be oriented, and $E\!X$ is
equipped with an involution which inverts the orientation. Each oriented edge
is labelled by an element of a finite alphabet $\mathbf{\Sigma}$. The labelling
is assumed to be deterministic: edges with the same initial (resp. terminal)
vertex have distinct labels. Furthermore it is assumed that the group of
label-preserving automorphisms of $X$ acts quasi-transitively. For any vertex
$o$ of $X$, consider the language of all words over $\mathbf{\Sigma}$ which can
be read along self-avoiding walks starting at $o$. We characterize under which
conditions on the graph structure this language is regular or context-free.
This is the case if and only if the graph has more than one end, and the size
of all ends is $1$, or at most $2$, respectively.
