Learning Regular Languages with the TTT Algorithm

This post provides a tutorial of the TTT algorithm for inferring input grammars. Unlike the RPNI which I had posted before, and similar to L* this is an active algorithm. That is, we assume that we can query the blackbox program to check whether an input is accepted or not.

This is part of my ongoing effort to document various algorithms relating to grammars including various algorithms for parsing, random sampling of fixed size strings, and grammar fuzzing.

I am looking for feedback on structure as well as content as before. The content is oriented toward software engineering students with limited knowledge or interest in formal theory. The implementation prioritizes clarity over speed.

Note: Pyodide takes a little time to initialize, but it should be faster to initialize than spinning up the binder service from Jupyter (but slower to execute).