This tutorial introduces Angluin’s L-star algorithm with PAC learning for inferring input grammars of blackbox programs in Python. The algorithm allows us to learn the input specification of a blackbox program, where the program indicates if the input was accepted or not. The tutorial explains the concept of observation tables and how they can be used to reconstruct the DFA or grammar of the program. It also discusses the properties of closedness and consistency that the observation table should satisfy. The tutorial provides step-by-step instructions and code snippets to implement the L-star algorithm in Python.
https://rahul.gopinath.org/post/2024/01/04/lstar-learning-regular-languages/