1
$\begingroup$

I have to create an NFA that accepts the following language L with no more than 15 states.

$L = \{a^n \mid n \geq 1$ and $n \mod105 \neq 0 \}$.

To me it seems that all multiples of 105 have the same properties:

  • sum of digits is divisible by 3
  • the last digit is 0 or 5

I would appreciate if someone could help me here.

$\endgroup$
  • $\begingroup$ Múltiples of 15 have the properties you list. $\endgroup$ – Peter Taylor May 15 at 5:39
3
$\begingroup$

Here is a hint.

$L$ is the union of the following three languages.

  • $L_3=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 3}\}$,
  • $L_5=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 5}\}$,
  • $L_7=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 7}\}$.

Construct the DFA for the above three languages. Then combine them together.


Exercise. (It may take some time to do this exercise.) Show that no NFA with less than 15 states accepts $L$ exactly.

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