1
$\begingroup$

I have been working on the following homework question, and I just can't seem to make any progress:

Construct a finite automaton having fewer than 36 states that recognizes the language $\{s \in a^* : \operatorname{gcd}(|s|, 504) \geq 6\}$, where $|s|$ is the length of $s$.

So far I have been trying to figure out a regular pattern in $504$ and have broken it down to the prime factorization $504 = 2^3 \cdot 3^2 \cdot 7$, which means that all divisors must be multiples of 2, 3, or 7. However I don't know how to create the finite automaton (NFA or DFA). Any help is appreciated!

$\endgroup$
4
$\begingroup$

The number $504$ has $4\cdot3\cdot2=24$ divisors: $$1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 18, 21, 24, 28, 36, 42, 56, 63, 72, 84, 126, 168, 252, 504$$ Out of these, $20$ are at least $6$: $$ 6, 7, 8, 9, 12, 14, 18, 21, 24, 28, 36, 42, 56, 63, 72, 84, 126, 168, 252, 504$$ For an integer $n$, $\operatorname{gcd}(n,504) \geq 6$ iff $n$ is a multiple of one of these numbers. To check this, we don't really need to go over all $20$ possibilities. For example, if $n$ is divisible by $12$ then it is also divisible by $6$, so we can remove $12$ from the list. The list narrows down to only $4$ options: $$ 6,7,8,9 $$ That is, $$ \operatorname{gcd}(n,504) \geq 6 \Leftrightarrow 6 \mid n \text{ or } 7 \mid n \text{ or } 8 \mid n \text{ or } 9 \mid n $$ You can check the condition on the right using an NFA with $6+7+8+9 = 30$ states (or $31$ states if you do not allow multiple initial states).

$\endgroup$
3
  • $\begingroup$ Thanks Yuval that makes sense. So would this NFA just be showing numbers divisble by 6,7,8,9? $\endgroup$ – Rogue_DEstruction Feb 26 at 20:33
  • $\begingroup$ That’s what my answer seems to imply. $\endgroup$ – Yuval Filmus Feb 26 at 22:11
  • 1
    $\begingroup$ Note that \gcd is already predefined in LaTeX (and MathJax); you don’t have to write it with \operatorname. $\endgroup$ – Emil Jeřábek Feb 27 at 9:00

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.