Regular Expression

Definition

Let $A$ and $B$ be a formal language over $\Sigma$. The regular operations are:

1. Union: $A\cup B=\{x\mid x\in A\vee x\in B\}$
2. Concatenation: $A\circ B=\{xy\mid x\in A,y\in B\}$
3. Kleene Star: $A^{\ast }=\{x_1\dots x_k\mid k\ge 0,x_i\in A\}$

Closure

The class of regular languages is closed under these operations. And in-fact these operations are sufficient to expres all regular languages.

Remarks

The term regular expression in practical computing has expanded to no longer be expressible as a regular expression defined above, such as including context-free attributes.