Regular expression cheat sheet

Denotational semantics

[ ⁣[] ⁣]:=[ ⁣[ε] ⁣]:={ε}[ ⁣[a] ⁣]:={a}[ ⁣[ab] ⁣]:=[ ⁣[a] ⁣][ ⁣[b] ⁣][ ⁣[a+b] ⁣]:=[ ⁣[a] ⁣][ ⁣[b] ⁣][ ⁣[a] ⁣]:=[ ⁣[a] ⁣]\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: L1L2:={w1w2:w1L1,w2L2}L0:={ε}Ln:=LLn1L:=nN0Ln\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

n(a)=n()=n(r1r2)=n(r1)n(r2)n(r1+r2)=n(r1)n(r2)n(r)=\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

x1L:={a:xaL}x1a={εa=xaxx1ε=x1=x1(ab)={(x1a)b+x1bn(a)(x1a)botherwisex1(a+b)=(x1a)+(x1b)x1a=(x1a)a\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

a+b=b+aa+a=a+a=aa=a=εa=aε=aa(b+c)=ab+ac(a+b)c=ac+bcaa=a\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

ε=ε=aa=aa(a)=aε+aa=a(ab)a=a(ba)\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)=(ab)=(a+b)=a(ba)(a + b)^* = (a^* b^*)^* = (a^* + b^*)^* = a^*(ba^*)^*

General elimination rules

a+b={aL(b)L(a)bL(a)L(b)ab={aL(b)L(a)bL(a)L(b)\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: ab+(a+b)=(a+b)ε+(a+b)=(a+b)ababa+(a+b+c)=(a+b+c)(a+b)a=(a+b)\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+rpr=qpr = q + rp \Rightarrow r = qp^*

Copyright © 2019 — 2021 Alexander Mayorov. All rights reserved.