5
$\begingroup$

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!

Improve this question
$\endgroup$
11
  • $\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
    Commented Nov 21, 2018 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
    Commented Nov 21, 2018 at 14:13
  • $\begingroup$ @DavidRicherby Ah, quite right. Derp. (You quoted the wrong half of my comment, though. ;) ) $\endgroup$
    – Raphael
    Commented Nov 21, 2018 at 14:37
  • $\begingroup$ @Raphael Doh, negations. $\endgroup$
    – David Richerby
    Commented Nov 21, 2018 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.
    Commented Nov 21, 2018 at 18:25

3 Answers 3

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 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
    Commented Nov 22, 2018 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
    Commented Nov 22, 2018 at 1:19
  • $\begingroup$ If you want, you can add the remark to your own answer. $\endgroup$
    – Hendrik Jan
    Commented Nov 22, 2018 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.
    Commented Nov 22, 2018 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
    Commented Nov 22, 2018 at 15:11
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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.
    Commented Nov 22, 2018 at 8:14
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ However, the language of even-length words only needs two states. $\endgroup$
    – John L.
    Commented Nov 22, 2018 at 15:29

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.