Bottom Line Up Front: I got my ILP system, Poker (vanilla/lib/poker at master · stassa/vanilla · GitHub), to learn the following DCGs for the Context-Sensitive language a^nb^nc^n.
% Grammar 1
s --> a, b, c.
s --> inv_1, c.
inv_1 --> a, inv_2, s.
inv_2, a --> a, inv_2.
inv_2, b --> b, b.
% Grammar 2
s --> a, b, c.
s --> inv_1, s, c.
inv_1 --> a, inv_2.
inv_2, a --> a, inv_2.
inv_2, b --> b, b.
% Grammar 3
s --> a, b, c.
s --> inv_1, s, c.
inv_1 --> a, inv_2.
inv_1, a --> a, inv_1.
inv_2, b --> b, b.
Now the long vesrion.
A while ago I asked if anyone knew a way to write down the classic a^nb^nc^n Context-Sensitive Grammar (CSG) from Example 2.2. in Hopcroft & Ullman’s Formal Languages and their Relation to Automata. The earlier thread is here: Writing a CSG in DCG notation
Here’s the Hopcroft & Ullman grammar again, for reference, with numbered rules:
- S \rightarrow aSBC
- S \rightarrow aBC
- CB \rightarrow BC
- aB \rightarrow ab
- bB \rightarrow bb
- bC \rightarrow bc
- cC \rightarrow cc
I could not find a good answer to my question. I found several a^nb^nc^n DCGs online but none of them modelled after the Hopcroft & Ullman one. I even asked Claude, Gemini and ChatGPT, each of which came up with different, broken grammars, and a couple of correct ones, none of which matched the original.
The tricky bit is that the Hopcroft & Ullman DCG has the context sensitive rule 3: CB \rightarrow BC, that is really unclear how to translate into a DCG rule. This rule has no terminals on either side. This would be fine otherwise but neither B nor C have any rules that are not context-sensitive, nor do they resolve to any single terminals. To make matters worse, a^nb^nc^n strings do not include B and C. These are included in grammar derivations, but not in language strings. If you think about it, when a DCG rule is resolved, it resolves to a string of terminals. Nonterminals are sort of “resolved away” and never appear in any DCG derivation. That means there’s never a pair of tokens CB or BC to be matched by rule 3. So it’s very difficult to understand what CB \rightarrow BC should mean in terms of a DCG.
So I tried a few things out and eventually decided to try and represent the “context” of a context-sensitive rule using pushback lists. That way a nonteraminal symbol can be “pushed” into the input and then consumed from it later. This gave me the following almost direct transcription of Hopcroft & Ullman’s grammar:
:-discontiguous('C'//0).
:-discontiguous('B'//0).
'S1'(Ps) --> { once( phrase('S', Ps)) }.
'S' --> [a], 'B', 'C'.
'S' --> [a], 'S', 'B', 'C'.
'C', ['B1'] --> 'B', 'C'.
'B' --> [b].
'C' --> [c].
'B', [a] --> [a, b].
'B', [b] --> [b, b].
'C', [c] --> [b, c].
'C', [c] --> [c, c].
'B' --> ['B1'].
You can call this grammar this way, length-bounded (otherwise it goes infinite):
102 ?- length(Ps,N), phrase('S1'(Ps),[]).
Ps = [a, b, c],
N = 3 ;
Ps = [a, a, b, b, c, c],
N = 6 ;
Ps = [a, a, a, b, b, b, c, c, c],
N = 9 ;
Ps = [a, a, a, a, b, b, b, b, c, c, c, c],
N = 12 ;
Ps = [a, a, a, a, a, b, b, b, b, b, c, c, c, c, c],
N = 15 .
Unfortunately this grammar over-generates, and that’s the reason for the extra rule with the once/1 call. Additionally, reordering the rules will make them generate incorrect strings first.
Worse, it doesn’t actually need the four context-sensitive rules that resolve to terminal strings:
'B', [a] --> [a, b].
'B', [b] --> [b, b].
'C', [c] --> [b, c].
'C', [c] --> [c, c].
If you remove those and make the same query you get the same result.
Finally, it’s reaaaaly slow. Check this out:
103 ?- length(Ps,N), 0 is N mod 3, time( phrase('S1'(Ps),[]) ).
% 18 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 24 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, b, c],
N = 3 ;
% 177 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, b, b, c, c],
N = 6 ;
% 3,876 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, b, b, b, c, c, c],
N = 9 ;
% 79,899 inferences, 0.000 CPU in 0.005 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, b, b, b, b, c, c, c, c],
N = 12 ;
% 1,476,502 inferences, 0.062 CPU in 0.067 seconds (93% CPU, 23624032 Lips)
Ps = [a, a, a, a, a, b, b, b, b, b, c, c, c, c, c],
N = 15 ;
% 25,469,573 inferences, 1.109 CPU in 1.106 seconds (100% CPU, 22958488 Lips)
Ps = [a, a, a, a, a, a, b, b, b, b, b, b, c, c, c, c, c, c],
N = 18 ;
% 420,785,408 inferences, 18.297 CPU in 18.372 seconds (100% CPU, 22997665 Lips)
Ps = [a, a, a, a, a, a, a, b, b, b, b, b, b, b, c, c, c, c, c|…],
N = 21 .
So this is just not a very good grammar at all but it’s the best I’ve been able to come up with so far.
Now, the point of the exercise was to understand how to write CSGs in DCG notation but in a general way that can be applied to any CSG, not just a^nb^nc^n. Ultimately what I wanted to be able to do was to get an ILP system to learn CSGs using this general notation as inductive bias. The notation has to be general so that we don’t have to specify different inductive bias for each grammar we want to learn. In that sense the exercise seems to have paid off because the “pushback trick” seems to work as a general template for context-sensitive rules. With one small tweak: that we never push a nonterminal in the input string, unless it’s a pre-terminal (i.e. of the form a --> [b]).
So I guess this is what one can expect in the age of AI, but after all that (and more) fancy footwork I got my ILP system Poker to learn the following a^nb^nc^n grammars, all of them in a variant of Kuroda Normal Form (KNF) expressed as second-order DCG rules with pushback lists.
% Grammar 1
s --> a, b, c.
s --> inv_1, c.
inv_1 --> a, inv_2, s.
inv_2, a --> a, inv_2.
inv_2, b --> b, b.
% Grammar 2
s --> a, b, c.
s --> inv_1, s, c.
inv_1 --> a, inv_2.
inv_2, a --> a, inv_2.
inv_2, b --> b, b.
% Grammar 3
s --> a, b, c.
s --> inv_1, s, c.
inv_1 --> a, inv_2.
inv_1, a --> a, inv_1.
inv_2, b --> b, b.
All three grammars use the same three pre-terminals for a,b,c as follows:
a --> [a].
b --> [b].
c --> [c].
Those are given to Poker as “background knowledge”. They can be automatically extracted from the language strings given as examples.
The non-terminal symbols named inv_1 and inv_2 are invented predicates, automatically created by the system. I will be honest and say I don’t yet fully understand the three grammars because I haven’t spent much time tracing them and scratching my head and whatnot, so I don’t know what the invented predicate symbols really mean.
All three grammars were learned from three positive examples of a^nb^nc^n in DCG form, as follows:
s([a,b,c],[]).
s([a,a,b,b,c,c],[]).
s([a,a,a,b,b,b,c,c,c],[]).
Poker automatically generates new, unlabelled examples, and labels them to refine an initial hypothesis. Poker needed to generate 60,000 unlabelled examples, and label them, to learn these three grammars above (which it learned in one go).
You can test each of these three grammars by calling them depth-bounded, as before, otherwise they, too, will go infinite (I don’t think that can be avoided):
60 ?- length(Ps,N), phrase(abc:s,Ps).
Ps = [a, b, c],
N = 3 ;
Ps = [a, a, b, b, c, c],
N = 6 ;
Ps = [a, a, a, b, b, b, c, c, c],
N = 9 ;
Ps = [a, a, a, a, b, b, b, b, c, c, c, c],
N = 12 ;
Ps = [a, a, a, a, a, b, b, b, b, b, c, c, c, c, c],
N = 15 ;
Ps = [a, a, a, a, a, a, b, b, b, b, b, b, c, c, c, c, c, c],
N = 18
This time neither of the three grammars over-geneates, nor do they have redundant rules. Additionally, they parse considerably faster than my hand-crafted grammar:
62 ?- length(Ps,N), 0 is N mod 3, time( phrase(abc:s,Ps) ).
% 8 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, b, c],
N = 3 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, b, b, c, c],
N = 6 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, b, b, b, c, c, c],
N = 9 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, b, b, b, b, c, c, c, c],
N = 12 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, b, b, b, b, b, c, c, c, c, c],
N = 15 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, a, b, b, b, b, b, b, c, c, c, c, c, c],
N = 18 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, a, a, b, b, b, b, b, b, b, c, c, c, c, c|…],
N = 21 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, a, a, a, b, b, b, b, b, b, b, b, c, c, c|…],
N = 24 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, a, a, a, a, b, b, b, b, b, b, b, b, b, c|…],
N = 27 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, a, a, a, a, a, b, b, b, b, b, b, b, b, b|…],
N = 30 ;
% 7,995 inferences, 0.000 CPU in 0.003 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, a, a, a, a, a, a, b, b, b, b, b, b, b, b|…],
N = 33 ;
% 7,899 inferences, 0.000 CPU in 0.003 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, a, a, a, a, a, a, a, b, b, b, b, b, b, b|…],
N = 36 ;
% 8,949 inferences, 0.000 CPU in 0.004 seconds (0% CPU, Infinite Lips)
Ps = [a, a, a, a, a, a, a, a, a, a, a, a, a, b, b, b, b, b, b|…],
N = 39 .
% And so on
So it seems that ILP (or at least Poker) is better at writing DCGs than me!
A note on Kuroda Normal Form. Recall that a CSG is in KNF if each of its production is in one of the following forms:
AB \rightarrow CD
A \rightarrow BC
A \rightarrow B
A \rightarrow a
Where A,B,C,D are nonterminals and a is a terminal. The attentive reader may have noticed that the three grammars learned by Poker have rules with three literals on the RHS, which KNF does not allow, however those rules are equivalent to KNF rules in “folded” form.
For example, the following rule (found in each of the three Poker learned grammars):
s --> a, b, c.
-can be “folded” in two rules, with the introduction of a “bridge” nonterminal b1 as follows:
s --> a, b1.
b1 --> b, c.
Both of the new rules are in the form A \rightarrow BC which is in KNF. The variant of KNF I used as an inductive bias for Poker includes the “folded” form of KNF A \rightarrow BC to avoid having to invent too many nonterminals. That’s because allowing the system to invent more nonterminals increases the cost of learning.
And, well, that’s it. Morale of the story: ILP can learn CSGs.
… this is where I should say that no other machine learning system is known that can learn a CSG, even one as “easy” as a^nb^nc^n from just three positive examples, even if those examples include the base-case “abc”, and blah blah blah. But, who cares in this day and age where AI can talk to you.