Learning regular languages has long been a fundamental topic in computational learning theory. In this thesis, we present our contributions to exploring the learnability of regular languages and their representation class, deterministic finite automata (DFAs).;To study the learnability of regular languages in the context of machine learning, we first need to understand how humans learn and acquire a language. We consider a society which consists of n people (or agents), where pairs of individuals are drawn uniformly at random to interact. Each individual has a confidence level for a grammar and a more confident person supports the grammar with higher probability. A person increases her confidence level when interacting with another person supporting the grammar, and decreases her confidence level otherwise. We prove that with high probability the three-state binary signaling process reaches consensus after &THgr;(n log n) interactions in the worst case, regardless of the initial configuration. In the general case, the continuous-time binary signaling process in the limit will converge within O(r log nr) time (corresponding to O( nr log nr) interactions in expectation) if the initial configuration is monotone, where r is the number of confidence levels. In the other direction, we also show a convergence lower bound O (nr + n log n) on the number of interactions when r is large.;The class of shuffle ideals is an important sub-family of regular languages. The shuffle ideal generated by a string set U is the collection of all strings containing some string u epsilon U as a (not necessarily contiguous) subsequence. We study the PAC learnability of shuffle ideals and present positive results on this learning problem under element-wise independent and identical distributions and Markovian distributions in the statistical query model. A constrained generalization to learning shuffle ideals under product distributions is also provided. In the empirical direction, we propose a heuristic algorithm for learning shuffle ideals from given labeled strings under general unrestricted distributions.;As a representation class of regular languages, DFAs are one of the most elementary computational models in the study of computer science. We study the learnability of a random DFA and propose a computationally efficient algorithm for learning and recovering a random DFA from uniform input strings and state information in the statistical query model. A random DFA is uniformly generated: for each state-symbol pair (q epsilon Q, sigma epsilon Sigma), we choose a state q' epsilon Q with replacement uniformly and independently at random and let ϕ(q, sigma) = q', where Q is the state space, Sigma is the alphabet and ϕ is the transition function. The given data are string-state pairs (&khgr;, q') where &khgr; is a string drawn uniformly at random and q is the state of the DFA reached on input &khgr; starting from the start state q0. A theoretical guarantee on the absolute error of the algorithm in the statistical query model is presented.;Given that automaton graphs are out-regular, we generalize our DFA learning algorithm to learning random regular graphs in the statistical query model from random paths. In 'a standard label-guided graph exploration setting, the edges incident from a node in the graph have distinct local labels. The input data to the statistical query oracle are path-vertex pairs (&khgr;, upsilon) where &khgr; is a random uniform path (a random sequence of edge labels) and upsilon is the vertex of the graph reached on the path x starting from a particular start vertex upsilon&ogr;.
展开▼
