This section will be about learning automata and the \(L^*\) algorithm. The algorithm was first described in this 1987 paper. You can find the notes I use to discuss it here and the formal description of the algorithm here.

What are learning automata?

In this video, I describe at a high-level the idea of learning automata and why they might intuitively be useful.

Introducing the active learning problem tackled by the \(L^*\) algorithm

Now that we’re a bit more convinced that studying learning automata is worthwhile, I describe problem setup (i.e., the input and expected output) of the (L^*) algorithm.

The \(L^*\) observation table

In this video, I give a lower-level description of the (L^*) algorithm by describing how it uses its main data structure, the observation table, to create a candidate DFA for the teacher. I also describe the closed and consistent conditions necessary to ensure that an observation table can actually be converted to a DFA.

Running through an example of the \(L^*\) algorithm

Grab some paper and a pen as, in this video, we’ll be going through an example run of the (L^*) algorithm. We will start with some seed data: (\varepsilon \in L, a, b \notin L) and we will expand the observation table and seek validation from the teacher oracle.