Algorithmic learning of formal languages of the MTSLₖ class
Ignas Rudaitis
October 2021

In this thesis, we study a model of phonotactics. The model is stated in terms of formal language theory. Namely, it is the MTSLk class of languages (multiple tier-based strictly k-local). This approach to phonotactics admits a simple answer to the problem of how humans learn to distinguish phonotactically well-formed utterances from ill-formed ones in their infancy. The problem is non-trivial, because the only sources of learning input are adults, who do not normally utter phonotactically ill-formed strings at all. A possible learning strategy is constituted by the MTSL2IA algorithm, proposed by McMullin, Aksënova, and De Santo. Part of this thesis is dedicated to further developing this algorithm. While the original version operates with MTSL2 languages, our version relaxes the parameter (denoting the span of k-grams) to arbitrary k. The developed algorithm is presented in pseudocode, a reference to a Python implementation is provided, and its correctness is argued for. In the rest of the thesis, we present a novel pumping lemma for MTSL2 languages. Its validity had revealed itself during the preparation of the previously described portion of the thesis.
Format: [ pdf ]
Reference: lingbuzz/006272
(please use that when you cite this article)
Published in: BSc thesis, Vilnius University
keywords: phonotactics, subregular program, formal languages, phonology
Downloaded:140 times


[ edit this article | back to article list ]