This paper presents an unsupervised batch learning algorithm for phonotactic grammars without a priori Optimality-theoretic constraints (Prince and Smolensky 1993, 2004). The learner generalizes using the notion of natural class and a novel formalization of locality. This learner is applied to three case studies: (1) a language with total ATR harmony (e.g., Kalenjin), (2) a language where the feature ATR is contrastive (e.g., Akan), and (3) a language where the distribution of ATR depends on syllable structure (e.g., Javanese). The learner generalizes successfully in each case from surface forms. This leads to a novel, nontrivial hypothesis with respect to phonotactic constraints: they are all neighborhood-distinct.