2
$\begingroup$

I found this statement listed as a theorem in a textbook:

If L ⊆ Σ∗ is any language, then L is regular iff it has finitely many right derivatives. Furthermore, if L is regular, then all its right derivatives are regular and their number is equal to the number of states of the minimal DFA’s for L.*

Unfortunately, no proof was provided. Why is this statement true?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

See Janusz Brzozowski's 1964 paper Derivatives of Regular Expressions. This is theorem 5.2 in the paper, and the proof is in Appendix 2.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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