patternMinor
Proof that a minimal DFA for a finite language has exactly one trap state
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?
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.
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.