0
$\begingroup$

Is it possible to derive a grammar with iself? Or more precisely, is it possible to conceive a grammar which language contains that grammar?

For example, the Wikipedia article about BNF claims to represent the BNF syntax with BNF. But if we tried to derive BNF with it, we'd obtain the same BNF, but with each character quoted (double-quotes single-quoted and other characters double-quoted). It's understandable, but it's not exactly the same (actually it's like if the quoted characters were another alphabet).

Here is my attempt to define an unrestricted grammar (ignore white spaces):

  • P = p P | p ;
  • p = V n V = A ; ;
  • A = V | A | V ;
  • V = v V | ;
  • v = n | t ;
  • n = P | p | V | v | n | t ;
  • t = P | p | V | v | n | t | = | | | ; ;

Another one with less "special characters" (|, A, p, v, n and t are optional but improved readability):

  • P = V P V = V ; P ;
  • P = V V V = V ; P ;
  • P = V P V = V ; ;
  • P = V V V = V ; ;
  • V = P V ;
  • V = V V ;
  • V = P V ;
  • V = V V ;
  • V = = V ;
  • V = ; V ;
  • V = ;

And with a regex: ( [ P V P V = ; ]* [ P V ] [ P V P V = ; ]* = [ P V P V = ; ]* ; )+

So we need 3 alphabets to build it (normal for "special characters", bold for variables and code for terminals).

EDIT: Actually we need an infinite number of alphabet... If we try to derive it once, normal is replaced by bold, bold by code, but we need a new alphabet to replace code

Is it possible to derive it with only one alphabet?


EDIT: A question I'll ask in another post:

Is it possible to design a program able to learn a grammar with just its self-definition?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! What does "build a grammar with iself" mean? Can you give us a much smaller (minimal) example? That example is a lot to wade through. Also, please ask only one question per post (you can ask about building a program separately; but first please do a little research to read about grammar induction). $\endgroup$ – D.W. Jan 12 '17 at 17:24
  • $\begingroup$ No, it's not possible, because the symbols $\to$, $\epsilon$ and $|$ cannot appear in $\Sigma$. $\endgroup$ – David Richerby Jan 14 '17 at 16:12
  • $\begingroup$ @DavidRicherby Why not? $\endgroup$ – Raphael Jan 14 '17 at 22:31
  • $\begingroup$ @Raphael How will you tell, e.g., whether $S\to A|B$ means "expand $S$ to either $A$ or $B$" or "expand $S$ to the string $A$-pipe-$B$"? If you do it by replacing those symbols with something different, then the string you generate isn't the grammar you started with. $\endgroup$ – David Richerby Jan 14 '17 at 23:33
  • 1
    $\begingroup$ Well, what about a context-free grammar (no ambiguity with $\to$) without $\epsilon$ or $|$ which are optional (like in my second attempt)? $\endgroup$ – CidTori Jan 15 '17 at 7:55

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.