Learning formal languages
Here are references to a few textbooks which describe
the learning algorithms in detail and provide
the required background.
Here is a very readable book from one of the founders of the subject,
and winner of the Turing award for 2010.
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 are references to some papers on learning automata, grammars and graphs.
Probably approximately correct, Basic books, 2013
Learning regular sets from queries and counterexamples,
Information and computation,
Volume 75, 1987, pp 87-106.
Queries and concept learning,
Machine learning, Volume 2(4), 1987, pp 319-342.
Learning context-free grammars from structural data in polynomial time,
Theoretical computer science, Volume 76(2-3), 1990,
Efficient learning of context-free grammars from positive structural examples,
Information and computation, Volume 97, 1992,
Baruch Awerbuch, Margrit Betke, Ronald Rivest and Mona Singh,
Piecemeal graph exploration by a mobile robot,
Information and computation, Volume 152(2), 1999,
Alexander Clark and Rémi Eyraud,
Polynomial identification in the limit of substitutable context-free languages
J. Machine Learning Research, Volume 8, 2007,
Alexander Clark, Rémi Eyraud and Amaury Habrard,
Using contextual representations to efficiently learn context-free languages,
J. Machine Learning Research, Volume 11, 2010,