Let $ G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $ u_1, \ldots, u_n$ a set of $ n$ strings generated by $ G$ .

For finite $ n$ , it is always possible to find a regular grammar $ \hat G=(\hat V, \Sigma, \hat R, S)$ which generates the strings $ u_1, \ldots, u_n$ .

Intuitively, as $ n$ goes to infinity, we expect $ \hat G$ to get larger: my guess is that the cardinal of $ \hat R$ (and maybe also the cardinal of $ \hat V$ ?) would need to go to infinity.

Are there results which formalize this, e.g. by giving a lower bound on these cardinals as a function of $ n$ ?