Regular languages extended with reduplication: Formal models, proofs and illustrations
Skip to main content
eScholarship
Open Access Publications from the University of California

UCLA

UCLA Electronic Theses and Dissertations bannerUCLA

Regular languages extended with reduplication: Formal models, proofs and illustrations

Abstract

Total reduplication is common in natural language phonology and morphology. However,productive total reduplication requires computational power beyond context-free, while other phonological and morphological patterns are regular, or even sub-regular. Thus, existing lan- guage classes characterizing reduplicated strings inevitably include typologically unattested context-free patterns, such as reversals. This thesis introduces two ways of extending regular languages to incorporate reduplication. Firstly, we add copying as an expression operator and define regular copying expressions (RCEs) in a more restricted way. Secondly, we aug- ment finite-state machinery with the ability to recognize copied strings and introduce a new computational device: finite-state buffered machine (FSBMs). As a result, the class of reg- ular languages and languages derived from them through a primitive copying operation is characterized, named regular+copying languages (RCLs). We then examine and discuss the closure properties of this language class. As suggested by previous literature (Gazdar and Pullum, 1985, 278), regular+copying languages should approach the correct characterization of natural language word sets.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View