Nullability (Regular Expressions)
- by danportin
In Brzozowski's "Derivatives of Regular Expressions" and elsewhere, the function d(R) returning ? if a R is nullable, and Ø otherwise, includes clauses such as the following:
d(R1 + R2) = d(R1) + d(R2)
d(R1 · R2) = d(R1) ? d(R2)
Clearly, if both R1 and R2 are nullable then (R1 · R2) is nullable, and if either R1 or R2 is nullable then (R1 + R2)…