HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$

Submitted by: @import:stackexchange-cs··
0
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!

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

Context

StackExchange Computer Science Q#100366, answer score: 6

Revisions (0)

No revisions yet.