Semantics of Regular Expressions

Definition

• Let $R$ be a regex
• $\mathcal{L}(R)$ is the set of Strings in Full Language ${\Sigma }^{\ast }$ that match $R$

Matches

• $\mathcal{L}(\varnothing )=\varnothing$
• $\mathcal{L}(ϵ)=\{ϵ\}$
• $\mathcal{L}(c)=\{c\}$, $\forall c\in \Sigma$
• $\mathcal{L}((S+T))=\mathcal{L}(S)\cup \mathcal{L}(T)$
• $\mathcal{L}((ST))=\mathcal{L}(S)\mathcal{L}(T)$
• $\mathcal{L}(S^{\ast })=\mathcal{L}(S{)}^{\ast }$