0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.