# Self Generating Grammars - Does it have to be infinite recursion?

For brevity, let's redefine a grammar to be just the three-tuple $$(\Sigma_G, P_G, S_G)$$.

As usual, $$\Sigma_G$$ is the alphabet, $$P_G$$ are the production rules and $$S_G$$ is the start rule of $$G$$.

For our "special" instance of a grammar, which we call $$X$$:

Let's define our alphabet $$\Sigma_X$$ to contain the metasymbols

or rather "symbols that are indistinguishable to whoever will be parsing the definition"

themselves used to define grammars in the first place: $$\{\text{ }\pmb{\{},\text{ }\pmb{,}\text{ },\pmb{\}}, etc\}$$

Then, we can define $$P_X$$ as $$\{S_X \to \pmb{(}\Sigma_X\pmb{,}P_X\pmb{,}S_X\pmb{)}\}$$

Of course, $$\Sigma_X$$ actually expands to all the required metasymbols to define $$X$$ itself and any other alphabetic symbols used in the production rules of $$X$$.

As one can see, $$P_X$$ is not only a recursive definition, but it never meets an end.

Are there cleverer ways to construct a self-replicating grammar?

By self-replicating grammar, I mean a grammar whose only recognisable language is that which contains only the string which is used to define it in the first place.

• I can’t say I understand the question, but it seems you are trying to build a quine. – Emil Jeřábek Jul 1 '20 at 13:28
• I'll look into those. Essentially, I'm trying to define a grammar that generates it's own definition, if that makes sense. – Novicegrammer Jul 1 '20 at 13:44
• @EmilJeřábek these are pretty much what I was looking for, thank you – Novicegrammer Jul 1 '20 at 14:23