0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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

0

Reset to default

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.