Learning formal languages
Here are references to a few textbooks which describe
the learning algorithms in detail and provide
the required background.
-
Michael Kearns and Umesh Vazirani,
Introduction to computational learning theory, MIT press, 1994
-
Colin de la Higuera,
Grammatical inference, Cambridge University press, 2010
-
Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar,
Foundations of machine learning, MIT press, 2012
Here is a very readable book from one of the founders of the subject,
and winner of the Turing award for 2010.
-
Leslie Valiant,
Probably approximately correct, Basic books, 2013
Here are references to some papers on learning automata, grammars and graphs.
-
Dana Angluin,
Learning regular sets from queries and counterexamples,
Information and computation,
Volume 75, 1987, pp 87-106.
-
Dana Angluin,
Queries and concept learning,
Machine learning, Volume 2(4), 1987, pp 319-342.
-
Yasubumi Sakakibara,
Learning context-free grammars from structural data in polynomial time,
Theoretical computer science, Volume 76(2-3), 1990,
pp 223-242.
-
Yasubumi Sakakibara,
Efficient learning of context-free grammars from positive structural examples,
Information and computation, Volume 97, 1992,
pp 23-60.
-
Baruch Awerbuch, Margrit Betke, Ronald Rivest and Mona Singh,
Piecemeal graph exploration by a mobile robot,
Information and computation, Volume 152(2), 1999,
pp 155-172.
-
Alexander Clark and Rémi Eyraud,
Polynomial identification in the limit of substitutable context-free languages
,
J. Machine Learning Research, Volume 8, 2007,
pp 1725-1745.
-
Alexander Clark, Rémi Eyraud and Amaury Habrard,
Using contextual representations to efficiently learn context-free languages,
J. Machine Learning Research, Volume 11, 2010,
pp 2707-2744.