3
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.