We skip all sections related to grammars for now.

Regular Expressions

Formal Definition of a Regular Expression

Let $\Sigma$ be a given alphabet. Then...

  1. $\empty$, $\lambda$, and $a \in \Sigma$ are all regular expressions. These are called primitive regular expressions.
  2. If $r_1$ and $r_2$ are regular expressions, so are $r_1 + r_2$, $r_1 \cdot r_2$, $r_1^*$, and $(r_1)$.
  3. A string is a regular expression iff if it can be derived from the primitive regular expressions by a finite number of applications of the rules in (2).

Languages Associated with Regular Expressions

If $r$ is a regular expression, we say $L(r)$ denotes the language associated with $r$.

The language $L(r)$ denoted by any regular expression $r$ is defined by the following rules:

Regular Expression Set notation
$\empty$ the empty set
$\lambda$ $\{ \lambda \}$
$a$ (for every $a \in \Sigma$) $\{ a \}$
$L(r_1 + r_2)$ $L(r_1) \cup L(r_2)$
$L(r_1 \cdot r_2)$ $L(r_1) L(r_2)$
$L((r_1))$ $L(r_1)$
$L(r_1^*)$ $(L(r_1))^*$

Connection Between Regular Expressions and Regular Languages

For every regular language, there is a regular expression.

For every regular expression, there is a regular language.