---
Here is a grammar for a made up language:
sentence = "sob" subject (verb "ob" object | verb "ad" sentence | "ploj").
verb = "ab" | "pom"
object = "foo" | "bar"
Construct a few sentences, and show the sentence so far, and which rule and step of the rule you are currently applying. E.g. sentence= ""; rule=sentence; step="sob".---
Notice I did not explain the BNF syntax, which is reasonable as it'll have plenty of that in its training data. Notice that I also "forgot" to give it a production for the "subject" rule - leaving it with two choices: It can give up and tell me off, or it can do as best it can and let me know it's had to improvise.
Here's the first sentence construction:
---
First Sentence Construction:
sentence = "";
Rule: sentence; Step: "sob". sentence = "sob";
Rule: subject; Step: (choosing object as a subject for simplicity) "foo". sentence = "sob foo";
Rule: verb; Step: "ab". sentence = "sob foo ab";
Rule: (verb "ob" object | verb "ad" sentence | "ploj"); Step: "ob". sentence = "sob foo ab ob";
Rule: object; Step: "bar". sentence = "sob foo ab ob bar"; (Complete Sentence)
---
It has correctly applied the rules I did give, and opted to "fill in" "object" as a replacement for my missing "subject" rule. There are few enough rules this could be a fluke, but it's a better choice to guess at that substitution than verb or sentence, though hardly takes a genius.
Second:
---
Second Sentence Construction:
sentence = "";
Rule: sentence; Step: "sob". sentence = "sob";
Rule: subject; Step: "bar". sentence = "sob bar";
Rule: verb; Step: "pom". sentence = "sob bar pom";
Rule: (verb "ob" object | verb "ad" sentence | "ploj"); Step: "ad". sentence = "sob bar pom ad";
Rule: sentence; Step: "sob" (this starts a nested sentence). sentence = "sob bar pom ad sob";
Rule: subject; Step: "foo". sentence = "sob bar pom ad sob foo";
Rule: verb; Step: "ab". sentence = "sob bar pom ad sob foo ab";
Rule: (verb "ob" object | verb "ad" sentence | "ploj"); Step: "ob". sentence = "sob bar pom ad sob foo ab ob";
Rule: object; Step: "foo". sentence = "sob bar pom ad sob foo ab ob foo"; (Complete Sentence)
---
This is also correct, and it correctly points out that the arm it picked triggered a nested application of the `sentence` rule.
It stumbled on the third attempt:
---
Third Sentence Construction:
sentence = "";
Rule: sentence; Step: "sob". sentence = "sob";
Rule: subject; Step: "foo". sentence = "sob foo";
Rule: verb; Step: "pom". sentence = "sob foo pom";
Rule: (verb "ob" object | verb "ad" sentence | "ploj"); Step: "ploj". sentence = "sob foo pom ploj"; (Complete Sentence)
---
Note that there is a possible interpretation of the "|" operator which would make its sentence valid, so "technically" it could be, but it would involve (ver "ob" object | verb "ad" sentence | "ploj") to be interpreted as (verb (("ob object)|("ad" sentence)|"ploj")) and that's contrived.
So to answer you: It can, and it does, but not always consistently. One can choose to be disappointed it's not perfect, but for just handing it a grammar and asking it to reason about it with no example text or chances to "practice" whatsoever, I think it's doing quite well.
I've interviewed many software developers who'd struggle with a task like this.
When prodded about the third example, it picks a more reasonable interpretation of the "|", though it's explanation starts out with an error, but then given a correct explanation:
---
Q: How do you figure this? The full rule is "sob" subject (verb "ob" object | verb "ad" sentence | "ploj"). How do you figure the verb is allowed without being followed by either "ad" or "ob"?
A: Upon closer examination, you are correct to point out that the structure following "sob" subject must indeed involve a verb according to the rule provided. The full rule:
"sob" subject (verb "ob" object | verb "ad" sentence | "ploj"). indicates that the sentence must start with "sob", followed by a subject, and then either:
a verb followed by "ob" and an object,
a verb followed by "ad" and another sentence,
or the standalone term "ploj".
---
It goes on to give two correct alternatives to the erroneous one:
---
* "sob foo ploj" — where "ploj" follows directly after the subject without a verb, or * "sob foo ab ob bar" — where "ab" is the verb followed by "ob" and "bar" as the object.
---
While it's not perfect, it can very clearly "learn and reproduce multistep algorithms" to some extent. It also clearly needs to get better at it.
I personally think the more theory trained folks wonder if there will turn out to be some analogy with the corresponding towers of languages and machines recognizing them (regular languages, finite automata, push down automata, turing machines, for examples).
is an example covering the historical language classes and recognizers for them.
Perhaps LLMs and various architectures will turn out fitting what you describe.