Basic Operations of Regular Expression

This post introduces the basic five operations of regular expression.

A regular expression expresses a set of strings over the denoted alphabet.

Two Basic Expressions

Single Character

$$ ‘c ‘ \rightarrow \lbrace “c” \rbrace$$

Epsilon, which is empty string

$$ \epsilon \rightarrow \lbrace “” \rbrace $$

Three Compound Expressions

Union

$$ A + B \rightarrow \lbrace a | a \in A \rbrace \cup \lbrace b | b \in B \rbrace $$

Concatenation

$$ AB \rightarrow \lbrace ab | a \in A, b \in B \rbrace $$

Kleene Star, or iteration

$$ A^{*} \rightarrow \bigcup_{i \ge 0} A^{i} $$

Other Extensions

At least once

$$ A^{+} \rightarrow AA^{*} $$

Option

$$ A? \rightarrow A + \epsilon $$

Range

$$ ‘a ‘ + ‘b ‘ + ‘c ‘ \cdots ‘z ‘ \rightarrow [a-z] $$

Excluded Range

$$ complement~of~[a-z] \rightarrow [\hat{} a-z] $$