On regular copying languages
Keywords:reduplication, copying, finite-state machinery, queue automata
This paper proposes a formal model of regular languages enriched with unbounded copying. We augment finite-state machinery with the ability to recognize copied strings by adding an unbounded memory buffer with a restricted form of first-in-first-out storage. The newly introduced computational device, finite-state buffered machines (FS-BMs), characterizes the class of regular languages and languages de-rived from them through a primitive copying operation. We name this language class regular copying languages (RCLs). We prove a pumping lemma and examine the closure properties of this language class. As suggested by previous literature (Gazdar and Pullum 1985, p. 278), regular copying languages should approach the correct characteriza-tion of natural language word sets.
How to Cite
Copyright (c) 2023 Yang Wang, Tim Hunter
This work is licensed under a Creative Commons Attribution 4.0 International License.