<p>See Janusz Brzozowski's 1964 paper <a href="http://dl.acm.org/citation.cfm?id=321249" rel="noreferrer"><em>Derivatives of Regular Expressions</em></a>. This is theorem 5.2 in the paper, and the proof is in Appendix 2. </p>

CC BY-SA 3.0
2017-05-04T09:07:08.213Z
2017-05-04T09:07:08.213Z
Neel Krishnaswami
<p>I found this statement listed as a theorem in a textbook:</p>

<blockquote>
  <p>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.*</p>
</blockquote>

<p>Unfortunately, no proof was provided. Why is this statement true?</p>

<fl.formal-languages>
Regularity of language with finite number of right derivatives
SKala
# Regularity of language with finite number of right derivatives

(Asked by: username_0 on 2017-05-03)

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?

**Tags:** fl.formal-languages


---

## 1 answers

### Answer by username_1 on 2017-05-04. Score: 4 | Accepted answer

See Janusz Brzozowski's 1964 paper [*Derivatives of Regular Expressions*](http://dl.acm.org/citation.cfm?id=321249). This is theorem 5.2 in the paper, and the proof is in Appendix 2.


---

