Probabilistic context free grammars (PCFGs) constitute a computational model suitable for probabilistic systems which observe non-regular (yet context-free) behavior. They are vastly used in computational linguistics [1]}, natural language processing [2]} and biological modeling, for instance, in probabilistic modeling of RNA structures [3]}. Methods for learning PCFGs from experimental data have been studied for over half a century.
Unfortunately, there are various hardness results regarding learning context-free grammars in general and probabilistic grammars in particular.
It follows from [4]} that context-free grammars (CFGs) cannot be identified in the limit from positive examples, and from [5]} that CFGs cannot be identified in polynomial time using equivalence queries only. Both results are not surprising for those familiar with learning regular languages, as they hold for the class of regular languages as well. However, while regular languages can be learned using both membership queries and equivalence queries [6]}, it was shown that learning CFGs using both membership queries and equivalence queries is computationally as hard as key cryptographic problems for which there is currently no known polynomial-time algorithm [7]}. de la Higuera elaborates more on the difficulties of learning context-free grammars in his book [8]}.
Hardness results for the probabilistic setting have also been established. Abe and Warmuth have shown a computational hardness result for the inference of probabilistic automata, in particular, that an exponential blowup with respect to the alphabet size is inevitable unless \(\textbf {RP}= \textbf {NP}\)  [9]}.
