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.