On regularity of languages generated by copying systems (Q800098): Difference between revisions

A new kind of generative systems, called copying systems, is introduced. These systems are meant to be useful in the study of repetitions of subwords in words, a research field generated by \textit{A. Thue} [Über unendliche Zeichenreihen, Norske Videnskaps, Selsk. Skr., I. Mat. Nat. Kl. Kristiania 7, 1-22 (1906)]. A copying system is defined as an ordered pair \(G=(\Sigma,w)\), where \(\Sigma\) is a finite alphabet and w is a nonempty word over \(\Sigma\). The language it generates is \(L(G)=\{x\in\Sigma^+| w copy^*x\},\) where \(copy^*\) is called the copying relation. It is defined as the reflexive and transitive closure of the direct copying relation over \(\sum^+:x copy y\) iff \(x=uzv\) and \(y=uzzv\), for some words u, v, z over \(\Sigma\), where z is nonempty. The paper contains a theorem allowing to prove that certain copy languages are not regular. A specific example is also provided. The authors point out two further problems of immediate interest: ''1) a characterization of regular copy languages, and 2) the relationship of copying systems to their ''symmetric version'' (that is introducing a square xx as well as reducing it to x are allowed).''