Regular Expressions

Definition

Abstract Syntax

Regular expressions over alphabet $\Sigma$ are defined inductively:

Constructor	Syntax	Meaning
Null	$\varepsilon$	Matches the empty string only
Never	$\emptyset$	Matches nothing
Symbol	$a$ for $a \in \Sigma$	Matches the single symbol $a$
Union	$R_1	R_2$
Concat	$R_1 \cdot R_2$ or $R_1 R_2$	Matches $R_1$ followed by $R_2$
Star	$R^*$	Matches zero or more repetitions of $R$

Concrete Syntax

The typical concrete syntax uses:

• | for union (alternation)
• Juxtaposition for concatenation: ab means $a$ then $b$
• * for Kleene star
• () for grouping

Precedence (highest to lowest)

1. Star (*)
2. Concatenation (implicit)
3. Union (|)

The Language of a Regular Expression

Definition

Each regex $R$ denotes a language $L(R) \subseteq \Sigma^*$, defined inductively:

Regex $R$	Language $L(R)$
$\varepsilon$	$\{\varepsilon\}$
$\emptyset$	$\emptyset$
$a$	$\{a\}$
$R_1	R_2$
$R_1 R_2$	$L(R_1) \cdot L(R_2) = \{uv : u \in L(R_1), v \in L(R_2)\}$
$R^*$	$L(R)^* = \bigcup_{n \geq 0} L(R)^n$

Examples

Single Symbols

• $L(a) = \{a\}$
• $L(ab) = \{ab\}$
• $L(a|b) = \{a, b\}$

Kleene Star

• $L(a^*) = \{\varepsilon, a, aa, aaa, \ldots\}$
• $L((a|b)^*) = \Sigma^*$ (all strings over $\{a, b\}$)
• $L(\emptyset^*) = \{\varepsilon\}$

Combinations

• $L(a^*b^*) = \{a^n b^m : n, m \geq 0\}$
• $L((ab)^*) = \{\varepsilon, ab, abab, ababab, \ldots\}$
• $L(a(b|c)^*) = \{a, ab, ac, abb, abc, acb, acc, \ldots\}$

Idioms and Patterns

Every String

$(a|b)^* = \Sigma^* \text{ (when } \Sigma = \{a, b\})$

Strings Starting with $a$

$a(a|b)^*$

Strings Ending with $a$

$(a|b)^*a$

Strings Containing $a$

$(a|b)^*a(a|b)^*$

Even-Length Strings

$((a|b)(a|b))^*$

At Least One $a$

$(a|b)^*a(a|b)^*$

Exactly One $a$

$b^*ab^*$

Algebraic Laws

Union

• Commutative: $R|S = S|R$
• Associative: $(R|S)|T = R|(S|T)$
• Identity: $R|\emptyset = R$
• Idempotent: $R|R = R$

Concatenation

• Associative: $(RS)T = R(ST)$
• Identity: $R\varepsilon = R = \varepsilon R$
• Zero: $R\emptyset = \emptyset = \emptyset R$
• Distributive over union: $R(S|T) = RS|RT$ and $(R|S)T = RT|ST$

Star

• $\varepsilon^* = \varepsilon$
• $\emptyset^* = \varepsilon$
• $R^{**} = R^*$
• $R^* = \varepsilon | RR^*$

Limitations

Not all languages are regular. For example:

• $\{a^n b^n : n \geq 0\}$ is NOT regular
• $\{ww : w \in \Sigma^*\}$ is NOT regular
• Balanced parentheses are NOT regular

These require more expressive formalisms (context-free grammars, etc.).

---

Summary

• Regular expressions are built from atoms ($\varepsilon$, $\emptyset$, symbols) and constructors (union, concat, star)
• Each regex denotes a language $L(R)$
• Precedence: star > concat > union
• Useful for pattern matching, lexical analysis
• Not all languages are regular