The L* Algorihthm for Constructing Deterministic Finite Automatons



Friday, 16 September 2022, 16:00 to 17:00


  • A201


Suppose we are presented with a language like L = {x ∈ {0, 1}| The third to last bit is 1}. We can intuitively understand this language. Given a string we can quickly tell if it is in L or not. Coming up with a DFA for a language from scratch is somewhat more difficult.

The L* algorithm is one way of writing a formal method which we use in finding a DFA for a regular language. In this talk we will see a description of the L* Algorithm and a proof of correctness.