A regular expression $r$ matches a string $s$ provided $s\in L(r)$.

Two regular expressions are equivalent provided that:

Examples of Equivalences

$$\begin{array}{rl}(a+b)+c& \equiv a+(b+c)\\ a+a& \equiv a\\ a+b& \equiv b+a\\ (a\cdot b)\cdot c& \equiv a\cdot (b\cdot c)\\ c\cdot (a+b)& \equiv (c\cdot a)+(c\cdot b)\\ & \\ a\cdot a& \not\equiv a\\ a+(b\cdot c)& \not\equiv (a+b)\cdot (a+c)\end{array}$$

Corner Cases

$$\begin{array}{rl}a\cdot 0& \not\equiv a\\ a+1& \not\equiv a\\ 1& \equiv 0^{\ast }\\ 1^{\ast }& \equiv 1\\ 0^{\ast }& \not\equiv 0\end{array}$$

Simplification Rules

$$\begin{array}{rl}r+0& \equiv r\\ 0+r& \equiv r\\ r\cdot 1& \equiv r\\ 1\cdot r& \equiv r\\ r\cdot 0& \equiv 0\\ 0\cdot r& \equiv 0\\ r+r& \equiv r\end{array}$$

Semantic Derivative

The Semantic Derivative of a language $A$ w.r.t. a character $c$ is:

We may extend this definition to strings:

Example

Given $A=\{foo,bar,frak\}$ then $\begin{array}{rl}\text{Der }fA& =\{oo,rak\}\\ \text{Der }bA& =\{ar\}\\ \text{Der }aA& =\{\}\end{array}$

Brzozowski’s Algorithm

Whether a regular expression can match the empty string.

Derivative of Regular Expression

Negation of Regular Expressions

$\sim r$ is everything that $r$ cannot recognise

Proofs

A regular expression $r$ matches a string $s$ provided $s\in L(r)$.

$\forall rs.\text{matcher }sr$ if and only if $s\in L(r)$

Main properties:

• $\forall r.\text{nullable}(r)$ if and only if $[]\in L(r)$
• $\forall rc.L(\text{der }cr)=\text{Der }c(L(r))$

Inductive definition of regular expression

Regular expressions are inductively defined as:

$$\begin{array}{rl}r& ::=\text{0}\\ & |\text{1}\\ & |c\\ & |r_1\cdot r_2\\ & |r_1+r_2\\ & |r^{\ast }\end{array}$$Link to original

If we want to prove something, say a property $P(r)$, for all regular expressions $r$ then:

• $P$ holds for $\text{0}$, $\text{1}$, and $c$.
• $P$ holds for $r_1+r_2$ under the assumption that $P$ already holds for $r_1$ and $r_2$.
• $P$ holds for $r_1\cdot r_2$ under the assumption that $P$ already holds for $r_1$ and $r_2$.
• $P$ holds for $r^{\ast }$ under the assumption that $P$ already holds for $r$.

Example: assume $P(r)$ is the property that $\text{nullable}(r)$ if and only if $[]\in L(r)$

Base Case $P(0)$: prove $\text{nullable}(0)$ iff $[]\in L(0)$. The result of nullable is defined as false, and the result of $[]\in \{\}$ is also false, therefore this holds.

$P(1)$: prove $\text{nullable}(1)$ iff $[]\in L(1)$. The result of nullable is defined as true, and the result of $[]\in \{[]\}$ is also true, therefore this holds.

[.. etc]

Inductive Case $P(r_1+r_2)$: prove $\text{nullable}(r_1+r_2)$ iff $[]\in L(r_1+r_2)$.

$P(r_1):\text{nullable}(r_1)\text{ iff }[]\in L(r_1)$ $P(r_2):\text{nullable}(r_2)\text{ iff }[]\in L(r_2)$

The result of $\text{nullable}(r_1+r_2)$ is the result of $\text{nullable}(r_1)\vee \text{nullable}(r_2)$, and the result of $[]\in L(r_1+r_2)$ is the same as $[]\in L(r_1)\vee L(r_2)$ or otherwise $[]\in L(r_1)\vee []\in L(r_2)$.

[.. incomplete]