1
$\begingroup$

Is there a formal definition for a size of a context-free grammar? The only definition I have seen so far is on this wiki page:

The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side.

So, how does one define the size of a production rule's RHS?

For example, if I define my CFG as:

S : A
A : 'a' B | A
B : 'b'

What is the size of the production rule A?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ You gave a definition, apply it. Size of A is: 5. $\endgroup$ – saadtaame Apr 10 '13 at 16:50
  • $\begingroup$ That would mean the length of a production rule's RHS is the number of symbols? Is there a formal definition for this? $\endgroup$ – Naveneetha Vasudevan Apr 10 '13 at 17:01
  • 2
    $\begingroup$ There are several different definitions for the size of a grammar. The exact definition you use depends on your application. What's your application? (If it's homework, please ask your instructor for the definition that they expect.) $\endgroup$ – Yuval Filmus Apr 10 '13 at 17:03
  • $\begingroup$ What do you want to use the size for? That way we can help you find an appropriate definition. $\endgroup$ – saadtaame Apr 10 '13 at 17:04
  • $\begingroup$ Actually $A$ is LHS for two rules, one with RHS $aB$ (size 2, so size of the rule is 3) and one with RHS $A$ (RHS size 1, rule: size 2). $\endgroup$ – frafl Apr 10 '13 at 17:26
3
$\begingroup$

What is your intended application. The article you cited does give a definition of size. A production rule

T -> R

has size |R|+1, where |R| is the number of symbols in R. A more precise definition can be found on page 9 of this document.

This notion of size is meant to compare different grammars that produce the same language. In particular, in the article you cited, the notion of size is used to see that under grammar transformations, the size of the grammar can explode.

|cite|improve this answer
$\endgroup$

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.