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$ – mrk 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$ – mrk 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$
0
$\begingroup$

In formal language theory, the exact definitions of terms tend to vary.

For instance, context-free grammars as introduced by Chomsky couldn't have empty right-hand sides. They couldn't produce the empty string. Quite a few articles followed this; later on, it became more common to allow this. Usually, the difference is of little or no consequence, but sometimes, it matters.

The same is true for the size of a grammar. In most applications, the exact definition chosen doesn't make much of a difference; in some applications, it does.

This is why articles and textbooks on formal language theory always state their definitions explicitly. So just pick one that suits your needs, preferably one that already appears elsewhere.

| 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.