No notes for preliminary parts of lecture.

Basic Regular Expressions

We inductively define basic regular expressions as:

Strings are lists of characters, for example $[],abc$.

Language

A language (over an alphabet $S$) is a set of words over $S$.

For example, given $S=\{a,b,c,...,z\}$.

• $L_1=\text{ all English words}$
• $L_2=\text{ all Latin words}$
• $L_3=\{ghgkrf,oputj,erwwq\}$

Given $S=\{0,1\}$:

• $L_4=\{001,101010,111,1001\}$
• $L_5=\{0^n{1}^m|n\text{ is even},m\text{ is odd}\}$

Link to original

Concatenation

The concatenation of words $x$ and $y$ is the word $x$ followed by the word $y$, written $xy$. We can use the syntax $\text{foo}@\text{bar}=\text{foobar}$.

Formally, $A@B\stackrel{def}{=}\{s_1@s_2|s_1\in A\wedge s_2\in B\}$.

Link to original

We can also “concatenate” two languages, for example:

Corner Cases

$$\begin{array}{rl}A@\{[]\}& =A\\ A@\{\}& =\{\}\end{array}$$

Meaning of Regexes

For the purposes of this, we define $L$ as a function from regular expressions to sets of strings (languages), $L:\text{Rexp}=>\text{Set}[\text{String}]$.

As such:

The Power Operation

The $n\text{th Power}$ of a language:

Example

$$\begin{array}{rl}{A}^4& =A@A@A@A(@\{[]\})\\ A^1& =A(@\{[]\})\\ A^0& =\{[]\}\end{array}$$

The Kleene Star

The Kleene Star of a language is $A\star \stackrel{def}{=}{\bigcup }_{0\le n}{A}^n$.

This expands to:

• $A^0\cup A^1\cup A^2\cup A^3\cup A^4\cup \dots$
• $\{[]\}\cup A\cup A@A\cup A@A@A\cup \dots$