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) is nullable. It is unclear to me what the above clauses are supposed to mean, however. My first thought, mapping (+), (·), or the Boolean operations to regular sets is nonsensical, since in the base case,
d(a) = Ø (for all a ? S)
d(?) = ?
d(Ø) = Ø
and ? is not a set (nor is the return type of d, which is a regular expression). Furthermore, this mapping isn't indicated, and there is a separate notation for it. I understand nullability, but I'm lost on the definition of the sum, product, and Boolean operations in the definition of d: how are ? or Ø returned from d(R1) ? d(R2), for instance, in the definition off d(R1 · R2)?
