3
$\begingroup$

Task:

Input: DFA $M = (Z, Σ, δ, q_S, E)$
$T(M)$ := Language that $M$ accepts.
Question: Does $T(M)$ contain at least one word $w$ such that $|w| = n^2$ with $n \in \mathbb{N}$$ ?$

My attempt:

Since the language $\{w\in Σ^* \mid |w| = n^2 \} $is not regular. You cannot create DFA $M'$ which accepts this language and use it somehow.

If $M$ is finite (which is decidable) you can check each word so this is not a problem.

If $M$ is not finite there has to be a cycle from a productive state. I have drawn a couple simple DFAs and I have noticed that there is DFA's with cycles that don't contain such word $w$.

Then I tried to find the property of the cycle/DFA so that there has to be a $w$ with $|w| = n^2$ and noticed that the following equation has to be true: $$n^2 = d + ck$$ with $d$ being the distance from the initial state $q_s$ to an accepting state $q_e \in E$ and $c$ being the length of the cycle somewhere on the path from $q_s$ to $q_e$.

Therefore: $$\sqrt{d+ck} \in \mathbb{N}$$ However I don't know how to continue from here. Any help would be greatly appreciated!

$\endgroup$
6
  • 1
    $\begingroup$ Is $n$ an input of the problem? $\endgroup$
    – Nathaniel
    Jun 12, 2022 at 15:56
  • $\begingroup$ No it has to be any $n$ $\endgroup$ Jun 12, 2022 at 15:56
  • 1
    $\begingroup$ Also why is your equation $n^2 = d+ck$ and not $2^n = d + ck$? $\endgroup$
    – Nathaniel
    Jun 12, 2022 at 15:58
  • $\begingroup$ Thank you that is a mistake sorry. $\endgroup$ Jun 12, 2022 at 15:58
  • $\begingroup$ Rather than answering clarification questions in the comments, please edit the question to clarify, and make sure that the question reads well for someone who encounters the question for the first time and they can understand what is being asked without having to read the comments. $\endgroup$
    – D.W.
    Jun 12, 2022 at 21:54

1 Answer 1

5
$\begingroup$

Convert $M$ to an NFA over $\Sigma = \{a\}$ by renaming all labels on edges to $a$. The language accepted by the NFA has the same word lengths as $T(M)$. Convert the NFA to a DFA. After removing unreachable states, the DFA is a path leading to a cycle. This implies that the set of length of words in $T(M)$ is eventually periodic. This means that for some there exist some $k,m$ and sets $S \subseteq \{0,\ldots,k-1\}$ and $T \subseteq \{0,\ldots,m-1\}$ such that the lengths of word in $T(M)$ are $$ S \cup \bigcup_{i \in T} \{ nm + k + i : n \in \mathbb{N} \}. $$ We have reduced your problem to the following:

Given $a > 0$ and $b \ge 0$, decide whether $\{na + b : n \in \mathbb{N}\}$ contains a square.

If $na + b = r^2$ for some $r$ then $b \equiv r^2 \pmod{a}$, and so $b$ is a quadratic residue modulo $a$. Conversely, suppose that $b$ is a quadratic residue modulo $a$. Then there exists $r$ such that $b \equiv r^2 \pmod{a}$, say $r^2 = b + za$, where $z \in \mathbb{Z}$. For any $m \in \mathbb{N}$, we have $$ (ma + r)^2 = a(m^2a + 2mr) + r^2 = a(m^2 a + 2mr + z) + b. $$ Choosing $m = |z|$, this is of the form $na + b$ for some $n \in \mathbb{N}$.

We have shown that $\{na + b : n \in \mathbb{N}\}$ contains a square iff $b$ is a quadratic residue modulo $a$, which is a decidable property.

$\endgroup$
11
  • $\begingroup$ What's the meaning of k and m? That (and what you do with them) isn't clear to me. $\endgroup$ Jun 12, 2022 at 18:10
  • $\begingroup$ Here $m$ is the length of the period, and $k$ is the length of the part in the sequence which is not periodic. In terms of the graph of the DFA, it has a path of length $k$ leading to a cycle of length $m$. $\endgroup$ Jun 12, 2022 at 18:16
  • $\begingroup$ Thanks. And yes, I realized it must indeed only be a path+cycle and edited that out. I was thinking of the original DFA having two cycles of different lengths, for example one accepting lengths that are multiples of 3 and the other accepting multiples of 5. But since you converted to a DFA over a single letter, I realized it can't have "branches" and thus will be a cycle of length 15, with accepting states at the proper places. $\endgroup$ Jun 12, 2022 at 18:21
  • $\begingroup$ Your $na + b = r^2$ is the same as my $n^2 = ck + d$ correct? $\endgroup$ Jun 12, 2022 at 18:28
  • 2
    $\begingroup$ You can’t have multiple cycles. There is only one cycle. $\endgroup$ Jun 12, 2022 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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