This dissertation focuses on two important areas of machine learning research--regular grammar inference and constructive neural network learning algorithms;Regular grammar inference is the process of learning a target regular grammar or equivalently a deterministic finite state automaton (DFA) from labeled examples. We focus on the design of efficient algorithms for learning DFA where the learner is provided with a representative set of examples for the target concept and additionally might be guided by a teacher who answers membership queries. DFA learning algorithms typically map a given structurally complete set of examples to a lattice of finite state automata. Explicit enumeration of this lattice is practically infeasible. We propose a framework for implicitly representing the lattice as a version space and design a provably correct search algorithm for identifying the target DFA. Incremental or online learning algorithms are important in scenarios where all the training examples might not be available to the learner at the start. We develop a provably correct polynomial time incremental algorithm for learning DFA from labeled examples and membership queries. PAC learnability of DFA under restricted classes of distributions is an open research problem. We solve this problem by proving that DFA are efficiently PAC learnable under the class of simple distributions;Constructive neural network learning algorithms offer an interesting approach for incremental construction of near minimal neural network architectures for pattern classification and inductive knowledge acquisition. The existing constructive learning algorithms were designed for two category pattern classification and assumed that the patterns have binary (or bipolar) valued attributes. We propose a framework for extending constructive learning algorithms to handle multiple output classes and real-valued attributes. Further, with carefully designed experimental studies we attempt to characterize the inductive bias of these algorithms. Owing to the limited training time and the inherent representational bias, these algorithms tend to construct networks with redundant elements. We develop pruning strategies for elimination of redundant neurons in MTiling based constructive networks. Experimental results show that pruning brings about a modest to significant reduction in network size. Finally, we demonstrate the applicability of constructive learning algorithms in the area of connectionist theory refinement.