Can formal grammars generate other grammars?

0
votes

I'm in a models of computation class, and we're just covering formal grammars. As we've defined it, a formal grammar is:

  • Some terminal symbols
  • Some nonterminal symbols
  • A start symbol
  • Some production rules

Given that grammars generate strings, it seems possible that you could pick a grammar that would generate another grammar. A few minutes of searching doesn't seem to yield much discussion in this area. My questions mainly are:

  • Is this an interesting question in computer science?
  • Can you compact grammars by generating grammars that generate them, or is the complexity irreducible?
2
computer-sciencegrammarpushdown-automaton
Whether it is an interesting question is of course debatable. – Willem Van Onsem
@willem: if we say that a question $Q$ is interesting if there exists some observer $O$ such that $O is-interested-in Q$, then the existence of this post seems to resolve the debate, provided that we believe that Bronze is within "computer science". – rici
@Bronze: you might want to ask this question in a computer science site, such as cs.stackexchange.com. Here, you will mostly find programmers. These sets are not disjoint, except during working hours, but the probability of engagement might be higher over there. – rici

2 Answers

0
votes

There are a number of formalisms -- BNF notation, for example -- which describe grammars and which are themselves representable by strings in a context-free grammar.

But I'm not sure that is what you are looking for. A grammar does not (usually) exist to represent a single string; rather, a grammar describes a (usually infinite) set of strings, without ascribing any semantics.

The nature of "naming" means that the semantics of formalisms like BNF (or pretty well any programming language) cannot be captured with a context-free grammar. Associating a "name" in a string with the other occurrences of the same "name" is quintessentially context-sensitive.

Consequently, there is a CFL which is the set of representations of all grammars (with a given alphabet), but the vast majority of those representations do not corresoond to useful or even meaningful grammars. In a typical derived string, no symbol on the right-hand side of a production would actually appear on the left-hand side of any rule, and the requirement that they should could not be expressed in a CFG.

0
votes

The question of a grammar that generates another grammar is interesting enough that it has a name and some literature -- see https://en.wikipedia.org/wiki/Two-level_grammar and the links from there.

And yes, you can certainly achieve compaction, in that the generated grammar may be effectively infinite.