Let’s suppose the following grammar:

```
S → variable = math_expr
variable → a | b | c
math_expr → INT | function
math_expr → func_1() | func_2(INT, INT, INT, INT)
INT → 1 | 2 | 3 | 4 | 5
```

Since this grammar cannot generate an infinite number of programs (you should assume this for my problem), I want to know if there is some kind of formula that calculate the number of **COMPLETE** and **INCOMPLETE** programs that can be generated by a finite grammar.

In my own definition, a **complete program** is a program that does not have non-terminal nodes.

Examples: `b = func_2(2,4,3,3)`

, `a = func_1()`

An **incomplete program** is a program that does have non-terminal nodes.

Examples: `b = func_2(2,2,INT,INT)`

, `c = math_expr`

, `S`

At the moment, I am able to know the number of complete and incomplete programs by applying a Breadth-First Search (BFS) starting from the `S`

node.

However, because I’m working with search in program synthesis, it would be great to know the size of the domain without the need to do an exhaustive search on it.

**How can I find the number of complete and incomplete programs given only the grammar?**

**PS.**: In my original problem, I am working with program synthesis with a Domain Specific Language (DSL). I tagged CFG with the hope that the same applies, granted I’m not 100% sure.