Closure of regular languages are closed under certain cut operations

Let $f : \mathbb{N} \to \mathbb{N}$ be an integer function. For a language $L$, define

$$f(L) = \{w \mid \exists x : |x| = f(|w|) \text{ and } wx \in L\}$$

For example, if $f(n) = n$ this is just the "halving" operation, and regular languages are well known to be closed under this -- just simultaneously walk forwards and backwards (where the backwards walk tries all possible paths, like in the subset construction).

According to HMU, regular languages are also closed under taking the functions $2n, n^2, 2^n$. It is easy to see for $2n$, or any linear function for that matter - just walked backwards with whatever the speed. How can this be done for $n^2$ or $2^n$? It doesn't seem feasible to just increase the speed, since that would require remembering the number of steps taken so far.

Also, can we adapt the solution to get some general sufficient conditions on which $f$ has this property? (I doubt there are necessary and sufficient conditions, but would love to be proved wrong)

• What is "HMU"? A certain textbook? – Yuval Filmus Mar 1 '17 at 17:19
• Please state the question in your title. – reinierpost Mar 1 '17 at 17:29
• @YuvalFilmus. Presumably Hopcroft, Motwani, Ullman, Introduction to Automata Theory . . . – Rick Decker Mar 1 '17 at 18:39

Take a DFA $\langle Q,q_0,F,\delta \rangle$ for $L$. For every state $q \in Q$, it is known that $$N_q = \{ n : \delta(q,x) \in F \text{ for some |x|=n} \}$$ is an eventually periodic set. In these terms, we have $$f(L) = \bigcup_{q \in Q} \{ w : \delta(q_0,w) = q \text{ and } |w|+f(|w|) \in N_q\}.$$ A few simple arguments show that $f$ is admissible (the set of regular languages is closed under $f$) if for every modulus $m$, there is a DFA $\langle Q',q'_0,\delta' \rangle$ over the alphabet $\{0\}$ which "computes" $|w|+f(|w|) \bmod m$, in the sense that on input $0^n$, you can recover $n+f(n) \bmod{m}$ from $\delta'(q'_0,0^n)$. This, in turn, happens if for every modulus $m$, the function mapping $n$ to $n+f(n) \bmod{m}$ is eventually periodic. Since $n \bmod{m}$ itself is periodic, we conclude that:
A function $f$ is admissible iff for all $m$, the function $\psi_{f,m}(n) = f(n) \bmod{m}$ is eventually periodic.
The Chinese Remainder Theorem shows that it suffices to consider values of $m$ which are prime powers.
All polynomials are clearly admissible: if $f$ is a polynomial, then $\psi_{f,m}$ has period $m$. Exponential functions $a^n$ are also admissible: if $m=p^k$, then either $p \mid a$, in which case $\psi_{f,m}$ is eventually zero, or $(p,a)=1$, in which case Euler's formula shows that $\psi_{f,m}$ has period $\varphi(m)$.
• @HendrikJan Kozen has an extra condition that I seem to have missed, C4(ii). My condition is only C4(i). Perhaps C4(ii) appears when doing all the proofs carefully. In any case, C4(ii) is not needed if $f$ is monotone. – Yuval Filmus Mar 2 '17 at 1:11