Skip to main content
1 of 3
Andrej Bauer
  • 48.8k
  • 11
  • 131
  • 240

You are looking for regular tree grammars. Here is the basic idea.

It is useful to think if syntactic expressions as abstract syntax trees. In our case we are looking for a tree $\alpha$ which satisfies the equation $$\alpha = \alpha + 1$$ The tree is infinite, but it is also regular (both intuitively and in a precise formal sense):

enter image description here

In general you might want to solve a system of such equations, for instance \begin{align*} \alpha &= \beta + \gamma \\ \beta &= 1 + \beta \\ \gamma &= (\gamma + \beta) \end{align*} gives the infinite epression $\alpha$ indicated by $$ (1 + (1 + (1 + \cdots))) + ((\cdots + (1 + (1 + (1 + \cdots)))) + (1 + (1 + (1 + \cdots)))). $$

Andrej Bauer
  • 48.8k
  • 11
  • 131
  • 240