Actually, I wasn't thinking of any specific methods, but now that you mentioned it, Inductive Logic Progamming (the subject of my PhD - see my comment about being biased) is a fine example.

For a slightly more impartial opinion, here's a DeepMind paper that performs neural ILP: https://deepmind.com/blog/learning-explanatory-rules-noisy-d...

The authors begin by extolling the virtues of ILP, including its generalisation abilities, as follows:

Second, ILP systems tend to be impressively data-efficient, able to generalise well from a small handful of examples. [1]

You can find more references to the generalisation power of ILP algorithms sprinkled throughout that text and in any case the entire paper is about getting the "best of both worlds" between ILP's generalisation, interpretability, ability for transfer learning and data efficiency and deep learning's robustness to noise and handling of non-symbolic data (I disagree about these last two bits with the authors, but, OK).

From my part, below is an example of learning a general form of the (context-free) a^nb^n grammar from 4 positive and 0 negative examples, using the Meta-Interpretive Learning system Metagol (a state-of-the-art ILP learner, referenced in the DeepMind paper; my PhD research is based on Metagol). You can clone metagol from its github page:

https://github.com/metagol/metagol

Metagol is written in Prolog. To run the example, you'll need a Prolog interpreter, either Yap [2] or Swi-Prolog [3]. And Metagol.

Copy the code below into a text file, call it something like "anbn.pl" and place it, e.g. in the "examples" directory in metagol's root directory.

  % Load metagol
  :-['../metagol']. % e.g. place in metagol/examples.
  
  % Second-order metarules providing inductive bias
  metarule([P,Q,R], ([P,A,B]:- [[Q,A,C],[R,C,B]])).
  metarule([P,Q,R], ([P,A,D]:- [[Q,A,B],[P,B,C],[R,C,D]])).
  
  % Grammar terminals, provided as background knowledge
  'A'([a|A], A).
  'B'([b|A], A).
  
  % Terminals actually declared as background knowledge primitives
  prim('A'/2).
  prim('B'/2).
  
  % Code to start training
  learn_an_bn:-
  	% Example sentences in the a^nb^n language
  	Pos = ['S'([a,a,b,b],[])
  	      ,'S'([a,b],[])
  	       % ^^ Place second to learn clauses in terminating order
  	      ,'S'([a,a,a,b,b,b],[])
  	      ,'S'([a,a,a,a,b,b,b,b],[])
  	      ]
  	% You can actually learn _without_ any negative examples.
  	,Neg = []
  	,learn(Pos, Neg).

Load the file into Prolog with the following query:

  [anbn].

Finally, start training by calling learn_an_bn:

  ?- learn_an_bn.
  % learning S/2
  % clauses: 1
  % clauses: 2
  'S'(A,B):-'A'(A,C),'B'(C,B).
  'S'(A,B):-'A'(A,C),'S'(C,D),'B'(D,B).
  true .

That should take a millisecond or two, on an ordinary laptop.

You can test the results by copy/pasting the two clauses of the predicate 'S'/2 into a prolog file (anbn.pl will do fine), (re)loading it and running a few queries like the following:

  ?- 'S'(A,[]). % Run as generator
  A = [a, b] ;
  A = [a, a, b, b] ;
  A = [a, a, a, b, b, b] ;
  A = [a, a, a, a, b, b, b, b] ;
  A = [a, a, a, a, a, b, b, b, b|...] ;
  
  ?- 'S'([a,a,b,b],[]). % Run as acceptor
  true .
  
  ?- 'S'([a,a,b,b,c],[]). % Run as acceptor with invalid string
  false.
  
  ?- 'S'([a,a,b,b,c],Rest). % Split the string to valid + suffix (Rest)
  Rest = [c] .

Note that the leraned grammar is a general form of a^nb^n, for example it accepts strings it's never even seen in testing (let alone training):

  ?- 'S'([a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,b,b,b],[]).
  true .

In any case, it's just a couple of first-order rules so it can be readily inspected to judge whether it's as general an a^nb^n grammar as can be, or not.

I guess you might not be much impressed by mere learning of a puny little grammar of a's and b's. You might be slightly more impressed if you know that learning a Context-Free language from only positive examples is actually impossible [4]. Metagol learns it thanks to the strong inductive bias provided by the two second-order metarules, at the start of the example. But, that's another huge can of worms. You asked me about generalisation :)

btw, no, you can't learn a^nb^n with deep learning- or anything else I'm aware of. The NLP people here should be able to confirm this.

_________________________

[1] https://arxiv.org/pdf/1711.04574.pdf

[2] http://www.dcc.fc.up.pt/~vsc/Yap/ (Yap is fastest)

[3] http://www.swi-prolog.org/ (Swi has more features)

[4] https://scholar.google.gr/scholar?hl=en&as_sdt=0%2C5&q=langu...

Well, actually, it is possible - but you need infinite examples or an Oracle already knowing the language.