4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SpooFwen Nov 4 '18 at 9:39
0
$\begingroup$

$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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – xskxzr Nov 4 '18 at 6:55
  • $\begingroup$ 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))$. $\endgroup$ – user95925 Nov 4 '18 at 12:08
  • $\begingroup$ And you are repeating my idea in details in your answer. Ok, more TeX typesettings may get accepted easier. $\endgroup$ – user95925 Nov 4 '18 at 12:10
  • $\begingroup$ 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. $\endgroup$ – xskxzr Nov 4 '18 at 13:26
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.