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

Proof that a minimal DFA for a finite language has exactly one trap state

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dfafinitelanguagehasonetrapthatforstateminimal

Problem

Suppose $L$ is a language with a finite number of strings. We know that $L$ is regular. If $M$ is the minimal DFA for $L$, prove that $L$ has exactly one state that we can't exit if we enter it.

I know this statement is true because $L$ has a finite number of strings, so a string with a length longer than the length of the longest string in $L$ (let's call that string $s$) will not be accepted by $M$. Also, the last state that $s$ lands on cannot go to any other state which eventually leads to an accepting state.

Is there a better more solid way to prove this?

Solution

Recall that in the minimal DFA, each state corresponds to an equivalence class of the Myhill–Nerode relation.

All words which are not a prefix of a word in $L$ form an equivalence class $X$, which satisfies the following: if $w \in X$ then $w\sigma \in X$ for all symbols $\sigma$. Therefore, the state corresponding to $X$ cannot be exited.

On the other hand, any other state in the minimal DFA can be exited, since we can always enter $X$ (for example, if we read more letters than the length of the longest word in $L$). Therefore the state corresponding to $X$ is the unique one which cannot be exited.

Context

StackExchange Computer Science Q#150603, answer score: 4

Revisions (0)

No revisions yet.