Brzozowski derivative

In 1964 Brzozowki proposed idea of derivatives for regular expressions. Note: he uses $\lambda$ for $\epsilon$, $\phi$ for $\emptyset$, $+$ for $\cup$, and $\&$ for $\cap$.

Formally derivative defined as $D_a(R) = \{ t \text{ | } at \in R \}$. Basically, it is the opposite of concatenation.

Basic example, let $L$ be $\{abc, abd, bcd\}$, then derivative by letter:

• $D_a(L) = \{bc, bd\}$
• $D_b(L) = \{cd\}$
• $D_c(L) = \{\}$
• $D_{ab}(L) = \{c, d\}$
• $D_{abc}(L) = \{\varepsilon\}$

More formally:

• $D_a(\emptyset) = \emptyset$
• $D_a(\epsilon) = \emptyset$
• $D_a(x) = \epsilon \text{ if } x = a$
• $D_a(x) = \emptyset \text{ if } x \neq a$
• $D_a(L_1 \cup L_2) = D_a(L_1) \cup D_a(L_2)$
• $D_a(L_1 \cap L_2) = D_a(L_1) \cap D_a(L_2)$
• $D_a(L^*) = D_a(L) \cdot L^*$
• $D_a(L_1 \cdot L_2) = D_a(L_1) \cdot L_2 \cup \delta(L_1) \cdot D_a(L_2)$
• $D_a(L^\prime) = D_a(L)^\prime$ - complement only defined in the absence of recursion

Definition of nullability function:

• $\delta(\emptyset) = \emptyset$
• $\delta(\epsilon) = \epsilon$
• $\delta(a) = \emptyset$
• $\delta(L_1 \cup L_2) = \delta(L_1) \cup \delta(L_2)$
• $\delta(L_1 \cap L_2) = \delta(L_1) \cap \delta(L_2)$
• $\delta(L_1 \cdot L_2) = \delta(L_1) \cdot \delta(L_2)$
• $\delta(L^*) = \epsilon$
• $\delta(L^\prime) = \epsilon \text{ if } \delta(L) = \emptyset$
• $\delta(L^\prime) = \emptyset \text{ if } \delta(L) = \epsilon$

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 ($\varepsilon$) than original language contains given word.