patternMinor
DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$
Viewed 0 times
dfaacceptsgeqbutthatrejects
Problem
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!
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!
Solution
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$.
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$.
Context
StackExchange Computer Science Q#100366, answer score: 6
Revisions (0)
No revisions yet.