What graphs on $\mathbb{N}$ can be encoded as regular languages? Suppose I represent the natural number 0 by &quot;x&quot;, and use the symbol &quot;s&quot; for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers into a formal language $V$:

$0 \mapsto x$, $1 \mapsto sx$, $2 \mapsto ssx$, $3 \mapsto sssx$, etc

So $V = \{x, sx, ssx, sssx, ... \}$ is a regular language generated by the regex $s^*x$.
Now, Suppose $G = (\mathbb{N},E \subset \mathbb{N} \times \mathbb{N})$ is a directed graph.  An edge $e = (n, m) \in E$.  I now define an encoding $\beta : E \rightarrow W$ of edges into a new language $W$ using the following encoding
$(n,m) \mapsto \alpha(n),\alpha(m)$ (i.e. concatenate the encoding of each number's encoding with a separating comma).  For example, $W((3,1)) = $&quot;sssx,sx&quot;

Question:  For what graphs $G$ of this type is $W$ a regular language?

Obviously if $E$ has a product structure such as $E = \{ (n, m) \ | \ n \in R_1, \ m \in R_2\}$ where each $R_i \subset \mathbb{N}$ corresponds to a regular language, then $W$ would be regular.  But what about more &quot;natural&quot; relations on $\mathbb{N}$?  In particular, here are two particular examples I am especially interested in:

Ex 1:  $E_1 = \{ (n, n+1) \ | \ n \in \mathbb{N} \}$.  Is $\beta(E_1)$ a regular language?


Ex 2:  $E_m' = \{ (n, n \times m) \ | \ n \in \mathbb{N} \}$ (i.e. an edge from each natural number to its product with a fixed natural number $m$).  Is $\beta(E_m')$ a regular language?

Any help is much appreciated :)
$\beta(E_1)$ is the language $s^nx,s^{n+1}x$. This language is straightforwardly not regular, by the pumping lemma.
If we assume that the language is regular, the pumping lemma tells us that there must exist some $p, q$ such that for all $n \ge p$, $s^{n+q}x,s^{n+1}x$ is also in the language. This is false, meaning that the language is not regular.
A similar argument also demonstrates that $\beta(E_2)$ is not regular, and more generally demonstrates that for a graph to be regular, for any $(n, m)$ in the graph with $n$ greater than some finite cutoff $p$, there must be infinitely many $n'$ such that $(n', m)$ is in the graph.
Since both $E_1$ and $E_2$ fail this condition, they are not regular.