Extended regular expression

Empty regex. Doesn't accept anything.

match empty s === False

Empty string. Note: different than empty.

match eps s === null s

Character.

Character range.

UTF8 character, i.e. may match multiple bytes.

Any character.

Concatenate regular expressions.

r <> empty === empty

empty <>  r === empty

( r <> s) <> t === r <> (s <> t)

r <> eps === r

eps <>  r === r

Union of regular expressions.

r \/ r === r

r \/ s === s \/ r

( r \/ s) \/ t === r \/ (s \/ t)

empty \/  r === r

r \/ empty === r

everything \/  r === everything

r \/ everything === everything

Intersection of regular expressions.

r /\ r === r

r /\ s === s /\ r

( r /\ s) /\ t === r /\ (s /\ t)

empty /\  r === empty

r /\ empty === empty

everything /\  r === r

r /\ everything === r

Kleene star.

star (star r) === star ( r)

star eps     ===  eps

star empty   ===  eps

star anyChar ===  everything

star (r \/ eps) === star r

star (char c \/ eps) === star (char c)

star (empty \/ eps) === eps

Kleene plus

plus r = r <> star r

Literal string.

UTF8 string

Complement.

complement (complement r) ===  r

Everything.

match everything s === True

We say that a regular expression r is nullable if the language it defines contains the empty string.

>>> nullable eps
True

>>> nullable (star "x")
True

>>> nullable "foo"
False

>>> nullable (complement eps)
False

Intuitively, the derivative of a language \(\mathcal{L} \subset \Sigma^\star\) with respect to a symbol \(a \in \Sigma\) is the language that includes only those suffixes of strings with a leading symbol \(a\) in \(\mathcal{L}\).

Whether ERE is (structurally) equal to empty.

Whether ERE is (structurally) equal to everything.