Construct a DFA $M$ with $\Sigma = \{a\}$ and max. 11 states so that $a^{23}\not\in L(M)$ but $\{a^i|i\geq 24\}\subset L(M)$.

I don't see how it is possible? Because it's a DFA and the alphabet only contains $a$, shouldn't I only be able to look at modulo 11? I could make 1 mod 11 not accepting but then $a^{34}$ would not be accepted as well.

EDIT: The prof confirmed it was a typo. We are looking for a NFA. Thanks everyone!

  • $\begingroup$ @HendrikJan Good point. Write any correct NFA, determinise, minimize. If it has more than 11 states, q.e.d. If not, there's your answer. $\endgroup$ – Raphael Nov 21 '18 at 14:03
  • 1
    $\begingroup$ @Raphael "If not, there's your answer." Not until you've tried all the other $2^{22}$ languages $L\subseteq a^*$ such that $L\cap\{a^i\mid i\geq 23\} = \{a^i\mid i>23\}$. The fact that one of the languages needs more than eleven states doesn't stop some other language being decidable with eleven or fewer. $\endgroup$ – David Richerby Nov 21 '18 at 14:13
  • $\begingroup$ @DavidRicherby Ah, quite right. Derp. (You quoted the wrong half of my comment, though. ;) ) $\endgroup$ – Raphael Nov 21 '18 at 14:37
  • $\begingroup$ @Raphael Doh, negations. $\endgroup$ – David Richerby Nov 21 '18 at 15:06
  • $\begingroup$ @MarkRegev, can you please credit the source of your question? We would like to know who or where this question comes from. It might turn out to be an error, a hoax or a typo in your question. $\endgroup$ – John L. Nov 21 '18 at 18:25

This is not possible. A DFA on a one symbol alphabet is a directed graph with out-degree 1. The walk one follows from the start state consists of a (possibly zero length) path followed by a cycle. As all sufficiently long strings are accepted, all states in the cycle must accept. If the DFA has at most 11 states, a walk of length 23 must be in the cycle, so it must accept.

More generally, if a DFA on one symbol rejects $a^n$ but accepts all $a^m$, $m>n$, then it must have at least $n+1$ symbols and start with a path of length $\ge n$, the $n$th state rejecting, followed by a cycle of accepting states of length $\ge 1$.

| cite | improve this answer | |
  • 2
    $\begingroup$ Finally I found a possibility to do it non-deterministically. If we have loops of length 5 and 6 with only the start state accepting we get strings of the length 0,5,6,10,11,12,15,16,17,18, [20,21,22,23,24,..] Last missing length is 19, so if we add a path to the loop with 4 letters we get a solution. The loops can be combined into 6 states so total of 10 states. This was trial and error. $\endgroup$ – Hendrik Jan Nov 22 '18 at 0:27
  • 1
    $\begingroup$ @HendrikJan BTW, this would be better posted as an answer. Even though it doesn't technically answer the question, it suggests the question should have said NFA, not DFA, and it answers that question. $\endgroup$ – Reinstate Monica Nov 22 '18 at 1:19
  • $\begingroup$ If you want, you can add the remark to your own answer. $\endgroup$ – Hendrik Jan Nov 22 '18 at 1:33
  • $\begingroup$ Slightly more generally, instead of accepting all $a^m$ for $m>n$, it is enough that the DFA accepts $a^{k}, a^{k+1}, \cdots, a^{k+n-1}$ for some $k\ge0$. $\endgroup$ – John L. Nov 22 '18 at 15:06
  • $\begingroup$ @Solomonoff'sSecret Must all states really accept once you enter the cycle? Is it not enough to prove using LTL that GF(Final) consider L = {a^2n | n>0} $\endgroup$ – JohEker Nov 22 '18 at 15:11

Solomonoff's answer points out that no such DFA exists.

This answer shows that we can build a nondeterministic finite automaton (NFA) that satisfies the requirement, indicating that the original problem might be intended for NFA instead of DFA.

The following nondeterministic finite automaton (NFA) has 7 states whose only accepting state is its start state. The language it accepts is $\{a^{5m+7n}\mid m,n\ge0\}=\{\epsilon,a^5, a^7, a^{10}, a^{12}, a^{14}, a^{15}, a^{17}, a^{19}, a^{20}, a^{21}, a^{22}\}\cup\{a^n\mid n\gt 23\}$. $(23 = 5*7-5-7)$ In other words, it rejects $a^{23}$ and accepts all $a^n$ for $n>23$.

An NFA made using kdickerson's automatonsimulator.com

The above image is made using automatonsimulator.com. This answer is motivated by Hendrik Jan's comment.

Interested readers can further prove that 7 is the minimal number of states in an NFA that rejects $a^{23}$ and accepts all $a^n$ for $n>23$.

| cite | improve this answer | |
  • $\begingroup$ If we replace the transition from s3 to s6 by a transition from s4 to the start state, the resulting equivalent NFA might be slightly easier to understand $\endgroup$ – John L. Nov 22 '18 at 8:14

Even stronger: Let L be any language containing a^{24} but not a^{23}.

After n a’s, 0 <= n < 24, we are in a state where we accept a^{24-n} but not a^{23-n}, so these 24 states are all different.

| cite | improve this answer | |
  • $\begingroup$ However, the language of even-length words only needs two states. $\endgroup$ – John L. Nov 22 '18 at 15:29

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.