We presented the problem of learning Deterministic Finite Automata from Queries. Learnability of DFA in the query model was first proved by Angluin (1987), and more efficient variations of Angluin's algorithm were proposed by Rivest&Schapire (1993) and Kearns&Vazirani (1994). Our presentation is slightly different: hopefully conceptually simpler, and easier to extend to the problem of learning Weighted Automata that we will discuss in the next session.
No exercises proposed today.
No comments:
Post a Comment