Regular expression cheat sheet

• Denotational semantics
• The nullable function
• Brzozowski derivatives
• Basic laws
• Other identities
  • Simplifying Kleene star
  • General elimination rules
• Arden’s Theorem

Denotational semantics

$\begin{aligned} [\![\varnothing]\!] &:= \varnothing \\ [\![\varepsilon]\!] &:= \{\varepsilon\} \\ [\![a]\!] &:= \{a\} \\ [\![a \cdot b]\!] &:= [\![a]\!] \cdot [\![b]\!] \\ [\![a + b]\!] &:= [\![a]\!] \cup [\![b]\!] \\ [\![a^*]\!] &:= [\![a]\!]^* \end{aligned}$

where the definitions of concatenation of languages and the Kleene stars are as follows: $\begin{aligned} L_1 \cdot L_2 &:= \{w_1 \cdot w_2 : w_1 \in L_1, w_2 \in L_2\} \\ L^0 &:= \{\varepsilon\} \\ L^n &:= L \cdot L^{n-1} \\ L^* &:= \bigcup_{n \in \mathbb{N}_0}{L^n} \end{aligned}$

The nullable function

$\begin{aligned} n(a) &= \bot \\ n(\varnothing) &= \top \\ n(r_1 \cdot r_2) &= n(r_1) \wedge n(r_2) \\ n(r_1 + r_2) &= n(r_1) \vee n(r_2) \\ n(r^*) &= \top \end{aligned}$

Brzozowski derivatives

$\begin{aligned} x^{-1} \cdot L &:= \{a : x \cdot a \in L\} \\ x^{-1}\cdot a &= \begin{cases} \varepsilon & a = x \\ \varnothing & a \neq x \end{cases} \\ x^{-1}\cdot \varepsilon &= \varnothing \\ x^{-1}\cdot \varnothing &= \varnothing \\ x^{-1}\cdot (a \cdot b) &= \begin{cases} (x^{-1} \cdot a) \cdot b + x^{-1} \cdot b & n(a) \\ (x^{-1} \cdot a) \cdot b & \text{otherwise} \end{cases} \\ x^{-1}\cdot (a + b) &= (x^{-1} \cdot a) + (x^{-1} \cdot b) \\ x^{-1} \cdot a^* &= (x^{-1} \cdot a) \cdot a^* \end{aligned}$

Basic laws

$\begin{aligned} a + b &= b + a \\ a + a &= a \\ \varnothing + a &= a \\ \varnothing \cdot a = a \cdot \varnothing &= \varnothing \\ \varepsilon \cdot a = a \cdot \varepsilon &= a \\ a(b + c) &= ab + ac \\ (a + b)c &= ac + bc \\ a^* a^* &= a^* \end{aligned}$

Other identities

$\begin{aligned} \varepsilon^* &= \varepsilon \\ \varnothing^* &= \varnothing \\ a a^* &= a^* a \\ (a^*)^* &= a^* \\ \varepsilon + aa^* &= a^* \\ (ab)^* a &= a(ba)^* \end{aligned}$

Simplifying Kleene star

$(a + b)^* = (a^* b^*)^* = (a^* + b^*)^* = a^*(ba^*)^*$

General elimination rules

$\begin{aligned} a + b &= \begin{cases} a & L(b) \subseteq L(a) \\ b & L(a) \subseteq L(b) \end{cases} \\ a^* b^* &= \begin{cases} a^* & L(b) \subseteq L(a) \\ b^* & L(a) \subseteq L(b) \end{cases} \end{aligned}$

Typical examples of the application of this rule: $\begin{aligned} ab + (a + b)^* &= (a + b)^* \\ \varepsilon + (a + b)^* &= (a + b)^* \\ a^* b^* aba + (a + b + c)^* &= (a + b + c)^* \\ (a+b)^* a^* &= (a+b)^* \end{aligned}$

Arden’s Theorem

$r = q + rp \Rightarrow r = qp^*$