# Prove regular languages are closed under f(n) = 2^n and f(n) = n^2

Suppose $$R$$ is a regular language, let $$f(R) = \{ w \mid \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$$, prove that $$f(R)$$ is regular for $$f(n) = 2^n$$ and for $$f(n) = n^2$$. I've been on this question for a while now, and I'm not really sure how to approach it. I only really know elementary techniques like Myhill-Nerode and constructing DFA/regex, so I probably won't understand solutions using more complex logical models of regular languages.

For $$f(n)=2^n$$:

Let $$M=(Q,\Sigma,\delta,q_0,F)$$ be the DFA recognizing $$R$$. Denote by $$\mathcal{G}$$ the set of functions from $$Q$$ to $$\mathcal{P}(Q)$$ (where $$\mathcal{P}(Q)$$ means the power set of $$Q$$), and for any $$g,h\in\mathcal{G}$$, denote by $$gh$$ the function defined as $$gh(\cdot)=\bigcup_{q\in h(\cdot)}g(q).$$

Construct a new DFA $$M'$$ of whose states each is labeled a pair $$(q,g)\in Q\times\mathcal{G}$$. The transition function $$\delta'$$ of $$M'$$ is defined as

$$\delta'((q,g),a)=\left(\delta(q,a),gg\right),$$

for all $$q\in Q, g\in\mathcal{G}, a\in\Sigma$$. The start state of $$M'$$ is $$(q_0,g_0)$$ where $$g_0$$ is defined as $$g_0(\cdot)=\{\delta(\cdot,a)\mid a\in \Sigma\}$$. The set of accept states of $$M'$$ is $$\{(q,g)\in Q\times\mathcal{G}\mid g(q)\cap F \neq \emptyset\}$$.

Now we claim that

After reading a word $$w$$, if $$M$$ reaches state $$q$$, then $$M'$$ reaches the state $$(q,g)$$, where $$g(\cdot)$$ represents the set of states $$M$$ can potentially reach when starting at state $$\cdot$$ then reading a word of length $$f(|w|)$$.

This cliam can be proven by mathematical induction on $$|w|$$. With this claim, we can see $$M'$$ indeed recognizes $$f(R)$$.

For $$f(n)=n^2$$, the proof is similar. In this case, each state of $$M'$$ is labeled a tuple $$(q,g_1,g_2)\in Q\times \mathcal{G}^2$$, the transition function becomes

$$\delta'((q,g_1,g_2),a)=\left(\delta(q,a),g_1g_0,((g_2g_1)g_1)g_0\right),$$

where $$g_0(\cdot)=\{\delta(\cdot,a)\mid a\in \Sigma\}$$ as above, the start stae becomes $$(q_0,I,I)$$ where $$I(\cdot)=\{\cdot\}$$, and the set of accept states becomes $$\{(q,g_1,g_2)\in Q\times\mathcal{G}\mid g_2(q)\cap F \neq \emptyset\}$$.

Also, our claim becomes

After reading a word $$w$$, if $$M$$ reaches state $$q$$, then $$M'$$ reaches the state $$(q,g_1,g_2)$$, where $$g_1(\cdot),g_2(\cdot)$$ respectively represent the set of states $$M$$ can potentially reach when starting at state $$\cdot$$ then reading a word of length $$|w|,|w|^2$$.

• Wow that's really clever way to sort of make the DFA "remember" |w|. I was under the impression that an approach like this won't work. – SpooFwen Nov 4 '18 at 9:39

$$f(R)$$ is regular since it can be decided by a one-tape TM in linear time.

Do a constant-sized matrix multiplication inside the TM's finite control.

The DFA transition can be viewed as a 0-1 matrix $$A$$ by forgetting the arc label. First comput $$A^n$$, then bounce back to compute $$A^{n^2}$$. Then proceed to run the DFA as usual to know the last state it ends after finishing readinv $$x$$. Query the computed $$A^{n^2}$$.

Similarly for $$2^n$$.

• The language $\{a^nb^n\mid n\in\mathbb{N}\}$ can be decided by a one-tape TM in linear time but it is not a regular language. – xskxzr Nov 4 '18 at 6:55
• Nope, it is impossible to decide that language by a one-tape TM in linear-time. You are confused with the two-tape one. This is exactly the proof of non-linear lowerbound for that language. In fact, an $\Omega(n^2)$ lowerbound for one-tape can be proved. For 2-tape, you can do it in $O(n\log(n))$. – user95925 Nov 4 '18 at 12:08
• And you are repeating my idea in details in your answer. Ok, more TeX typesettings may get accepted easier. – user95925 Nov 4 '18 at 12:10
• You are right DFA = linear time TM but the proof seems a bit tricky. In addition $\{a^n b^n\mid n\in\mathbb{N}\}$ can be decided by a one-tape TM in $O(n\log n)$ by moving the counter in the tape. – xskxzr Nov 4 '18 at 13:26

For this and similar problems you need to first prove a property of finite state machines: The set of lengths of strings that transition from one state to another is either a finite set of integers, or there is a k >= 1, and two finite sets X and Y such that every possible length is either in X, or is equal to n*k + y, where n >= 0 and y is an element of Y.

Second, if we know the lengths of all inputs going from state S to a fixed accepting state T, can we determine the set of integers k, such that after going from initial state to S, we can reach the accepting state after a total of f(n) steps?

As an example, if we took k steps from initial state to S,and there are 7j + 15 steps needed to reach an accepting state, and f(n)= n^2 then n^2 mod 7 = 0,1,4,2,2,4,1 so k+7j+15 = n^2 If k mod 7 is 7, 0 or 3.

And here it is essential that not only can we solve this for k, but the solution is easy enough that we can modify our stat machine to handle it.