Regular Expression

Regular expressions (commonly called regex) are a type of grammar that creates strings (here in the formulaic sense). In a sense, a regular expression is a mathematical formula that creates strings. They are especially useful in string pattern-matching. More formally, a regex defines a regular language

Definition §

Regular Expression ^definition

A regular expression, $R$, over an alphabet $\Sigma =\{a_1,a_2,\dots ,a_n\}$ is defined as:

$$R:=a_1|a_2|\dots a_n|ϵ|\varnothing |(R\cup R)|(R\circ R)|(R^{\ast })$$

• $\cup$ (sometimes replaced with $|$ ) means OR: $(1\cup 0)$ defines the language $L=\{0,1\}$
• $\circ$ means concatenation: $(0\circ 1)=(01)$ (commonly the circle is omitted) defines the language $L=\{01\}$
• ${}^{\ast }$ means the Kleene star: $0^{\ast }$ defines the language $L=\{ϵ,0,00,000,\dots \}$

$L(R)$ defines the (regular) language generated from the regex $R$

Some examples of regexes:

• $ca\circ (t\cup b\cup p)$ defines the language $L=\{cat,cab,cap\}$
• $0\circ 1^{\ast }$ defines the language $L=\{0,01,011,011,01111,\dots \}$

Since regexes borrow all the same operations on languages, we can ‘pull’ out the $L$:

• $L(a)=\{a\}$
• $L(ϵ)=\{ϵ\}$
• $L(\varnothing )=\varnothing$ (Pay attention! The empty word is not the empty set!)
• $L(R_1\cup R_2)=L(R_1)\cup L(R_2)$
• $L(R_1\circ R_2)=L(R_1{R}_2)=L(R_1)\circ L(R_2)$
• $L(R^{\ast })=(L(R){)}^{\ast }$

Binding Power §

Just like in formula parsing, regexes have a very, strict, well-formed syntax, that is unambiguous, as well as a slightly looser syntax. For example:

$$R_1=((a\circ b)\cup c)R_2=ab\cup c$$

In our looser syntax, we ignore unnecessary parentheses, as well as treat $a\circ b=ab$

$R_2$ defines the exact same language as $R_1$, but is much more simpler. However, this is only possible when we understand the binding powers of the operations for languages:

Expression Tree §

Like formula parsing, we can optionally construct an expression tree to visually see the hierarchy in a more complex regex:

Considered the regex below: %%🖋 Edit in Excalidraw, and the dark exported image%%

Theorems §

T1: A language is regular iff it can be described by a regular expression. ^t1

Let $L$ be a language. Then:

$$\text{L is a regular language}⟺\exists \text{regular expression, R},L(R)=R$$

Proof equivalence, we need to prove both 'sides': $L$ being regular implies that there is a regex $R$ that yields the same language and that if we have a regex $R$ for some language $L$, it implies that $L$ is regular.

Since this statement is an

Start by the left equivalence ($⟸$): $L$ is a regular language $⟸$ There is a regular expression $R$ that corresponds to $L$.

We can use the definition of a regular language:

So, we just need to construct a DFA that recognises $L$.

We use a proof by induction:

Base Case(s): $R=a\in \Sigma |ϵ|\varnothing$

We can construct trivial automata that recognise $L(R)$:

$R$	$L(R)$	Equivalent DFA
$a\in \Sigma$	$\{a\}$	%%🖋 Edit in Excalidraw, and the dark exported image%%
$ϵ$	$\{ϵ\}$	%%🖋 Edit in Excalidraw, and the dark exported image%%
$\varnothing$	$\varnothing$	%%🖋 Edit in Excalidraw, and the dark exported image%%
Inductive Step: $R=R\cup R|R\circ R|R^{\ast }$

We can use the existing proofs that union, concatenation and Kleene star are closed with respect to regular languages. Just use the same DFA used in the proofs of these theorems.

#todo finish both sides of implicaiton

Examples §

1: Deriving the equivalent language from a regular expression

Find the associated language of the regular expression given below:

$$((0\cup 1)\circ (0\circ 1){)}^{\ast }$$

Solution

When ‘parsing’ a regular expression, it helps to consider the innermost regex first.

• $(0\cup 1)$ gives the language $\{0,1\}$
• $(0\cup 1)\circ (0\cup 1)$ gives the language $\{0,1\}\circ \{0,1\}=\{00,01,10,11\}$
• Taking the Kleene star of that all binary strings of even length.