In 1964 Brzozowki proposed idea of derivatives for regular expressions. Note: he uses λ for ϵ, ϕ for ∅, + for ∪, and & for ∩.
Formally derivative defined as Da(R)={t | at∈R}. Basically, it is the opposite of concatenation.
Basic example, let L be {abc,abd,bcd}, then derivative by letter:
- Da(L)={bc,bd}
- Db(L)={cd}
- Dc(L)={}
- Dab(L)={c,d}
- Dabc(L)={ε}
More formally:
- Da(∅)=∅
- Da(ϵ)=∅
- Da(x)=ϵ if x=a
- Da(x)=∅ if x=a
- Da(L1∪L2)=Da(L1)∪Da(L2)
- Da(L1∩L2)=Da(L1)∩Da(L2)
- Da(L∗)=Da(L)⋅L∗
- Da(L1⋅L2)=Da(L1)⋅L2∪δ(L1)⋅Da(L2)
- Da(L′)=Da(L)′ - complement only defined in the absence of recursion
Definition of nullability function:
- δ(∅)=∅
- δ(ϵ)=ϵ
- δ(a)=∅
- δ(L1∪L2)=δ(L1)∪δ(L2)
- δ(L1∩L2)=δ(L1)∩δ(L2)
- δ(L1⋅L2)=δ(L1)⋅δ(L2)
- δ(L∗)=ϵ
- δ(L′)=ϵ if δ(L)=∅
- δ(L′)=∅ if δ(L)=ϵ
Brzozowki shows how derivatives can be used to construct Mealy and Moore automata (finite state machines). Also, he shows how identity rules can be used to simplify automata.
So in order to test if a string is in a language it is enough to take derivative by this word and if resulted language contains empty string (ε) than original language contains given word.