Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language.

For example:

rules_1 = [('s', ''), ('s', '(s)s')]

depths =  0, nodes_on_current_level =  1, nodes = ['s']

depths =  1, nodes_on_current_level =  2, nodes = ['', '(s)s']

depths =  2, nodes_on_current_level =  2, nodes = ['()s',  '((s)s)s']

depths =  3, nodes_on_current_level =  4, nodes = ['()', '()(s)s', '(()s)s', '(((s)s)s)s']

depths =  4, nodes_on_current_level =  6
depths =  5, nodes_on_current_level =  12 
depths =  6, nodes_on_current_level =  20
depths =  7, nodes_on_current_level =  40

It is clear that the number of nodes increases with depths. Dynamic branching factor.
Different production rules can create different number of nodes: s->() produces 0 nodes, s->s() produces 1 node, s->(s)s produces 2 nodes.
Not all production rules can apply for each node: A->B(), A->(), B->B(). For node 'A' there are 2 rules, for node 'B' only one rule.

Can you please suggest algorithm / formula how to count the number of nodes (in total and on provided depth) as a function of depth and any set of production rules? I need algorithm for nodes_on_current_level.

  • $\begingroup$ this seems like any other problem of counting nodes in a tree. You will have to generate the whole tree and save some extra parameters (like depth) at each node. Then you can easily traverse the tree to calculate what you need. $\endgroup$
    – Rinkesh P
    Jan 23 at 4:07
  • $\begingroup$ I want to get algorithm to calculate the number of nodes on each level without generating the whole tree. Just by inspecting production rules. Do you think it is impossible? $\endgroup$
    – Oleg Dats
    Jan 23 at 10:41
  • $\begingroup$ How do you plan on approaching the problem? Grammar is a finite set of rules while the language it generates can be finite/infinite, how do you plan on figuring out what productions a string uses without even looking at the string? I don't see a way, maybe someone can shed some light. $\endgroup$
    – Rinkesh P
    Jan 23 at 10:48


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.