It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L_0 \supseteq L$), production complexity (minimal possible $|P|$ for grammar $(N, \Sigma, P, S)$ generating $L$)... What are other kinds of grammar complexity studied in literature? How these complexities depend on each other?

  • $\begingroup$ I suppose, it is possible to measure context-free grammar complexity in terms of number of states of corresponded recursive state machine. Are you about context-free grammars? $\endgroup$ – gsv Jan 22 at 19:38
  • $\begingroup$ @gsv Generally speaking yes, but I specify these complexities for regular language; number of states doesn't seem to be to thing I want to study --- as for any n I can find a regular language which can be generated by CFG with one nonterminal and has n-state minimal accepting automata. $\endgroup$ – DG_ Jan 23 at 22:24

I think that among the most obvious measures are variable and production complexity. These are structural measures, in the sense there is for each k an infinitude of languages having measure k. And they are independent from each other, unless you consider the numbers for grammars in Chomsky normal form.

Another obvious measure is the total size of the grammar. Here you can compare required size in various normal forms, for example. It's also the thing to look at for grammar based compression. This measure is less a structural measure, but more a descriptional complexity measure. The textbook by M. Harrison on formal language theory (1978) has some coverage in chapter 4 of the early works on this by J. Gruska and others.

Here are a few pointers to the recent literature. I'm not aware of recent surveys, but maybe look at the cited references.

Jürgen Dassow, Ronny Harbich: Production Complexity of Some Operations on Context-Free Languages. DCFS 2012: 141-154

Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid: On the Complexity of Grammar-Based Compression over Fixed Alphabets. ICALP 2016: 122:1-122:14

Stefan Hetzl, Simon Wolfsteiner: On the cover complexity of finite languages. Theor. Comput. Sci. 798: 109-125 (2019)

EDIT (05/04/2021): An observation regarding the relation between number of variables and productions in context-free grammars: the left-hand side of every production from $P$ is a variable from $V$, so $|P|\ge |V|$, provided we assume (w.l.o.g.) that every variable is used in at least one production. Every finite language can be generated by a context-free grammar with just one variable (the start symbol), and with one production for each word – of which there are finitely many. On the other hand, there are finite languages for which the minimum number of productions required by any context-free grammar equals the number of words in the language (by work of Bucher, Maurer, Culik, Wotschke). This shows that the "production hierarchy" is more fine-grained than the "variable hierarchy".


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.