Which factors make the problem of inferring the grammar difficult? Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see ECCC Report: TR11-108, section 7, pp 25-31):


  Following the work of Kearns and Valiant, we now know that many
  natural learning problems — as an example, inferring the rules of a
  regular or context-free language from random examples of grammatical
  and ungrammatical sentences — are computationally intractable.


My question is: Which factors make the problem of inferring the grammar difficult? Is the introducing random examples of ungrammatical sentences? If so, what would happen if the condition of "random examples of grammatical and ungrammatical sentences" is replace with "random examples of grammatical sentences with probability p>0 and random examples of ungrammatical sentences with probability 1-p"?
Regarding the difficulty of learning grammars, let's stick to regular ones for concreteness. These are precisely the grammars/languages recognized by Deterministic Finite-state Automata (DFAs). The source of difficulty is purely computational; the statistical aspects are quite straightforward. 

If you were able to find the smallest DFA consistent with your finite sample, simple Occam/cardinality arguments guarantee that this will generalize very well (it's the "optimal" learner in some sense). See Theorems 2 and 3 of Graepel et al.
http://research.microsoft.com/pubs/65635/graepelherbrichtaylor05.pdf
for actual state-of-the-art bounds. 

However, finding such a small DFA is VERY hard (see Angluin, Gold, Pitt-Warmuth, etc):
http://www.sciencedirect.com/science/article/pii/S0019995878906836
http://web.mit.edu/6.863/www/spring2010/readings/gold67limit.pdf
http://dl.acm.org/citation.cfm?id=138042
[the latter even gives a hardness-of-approximation result].

But wait, it gets worse! Suppose you didn't care about a DFA and just wanted to learn the grammar in some representation (i.e., a mechanism for predicting the labels of test strings drawn from the same distribution as the training set).
If such an algorithm were to exist, and succeeded against all distributions, then it would also break RSA and related cryptographic primitives:
http://dl.acm.org/citation.cfm?id=697797