Power Spectra of Regular Languages

Given a real-valued sequence (Jq, Ci,. ..,(T v-i, the the correlation function R t) and Fourier Transformation may be defined in both a continuous and discrete form  

We give both forms here because, depending on the problem, either of the two forms may yield a simpler answer. Although the discrete form may appear a-priori to be the natural choice, for example, its discrete nature actually introduces some spurious periodicity into the resulting power spectra, thus washing away some of its characteristic features. We therefore follow Li [H87] in working mainly with the continuous forms of R t) and 

The energy spectral density function (or power spectrum) P f) is given by the absolute square of P f)  

It is a well known fact, called the Wiener-Khintchine Theorem [gardi85], that the correlation function and power spectrum are Fourier Transforms of one another  

---

Chapter 6 is a short primer on CA and language theory, and provides a basic discussion of formal language theory, the relationship between CA and formal language theory, power spectra of regular languages and reversible computation. 

H87] Li, W., Power spectra of regular languages and cellular automata . Complex Systems 1 (1987), 107-130. 

---