patternMinor
Decide whether regular language contains a word $w$ for which $|w| = n^2$
Viewed 0 times
regularlanguagewordcontainsdecideforwhichwhether
Problem
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!
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!
Solution
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.
$$ 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.
Context
StackExchange Computer Science Q#152295, answer score: 5
Revisions (0)
No revisions yet.