Regular Expression

These are Strings used to define search patterns of strings from a regex alphabet $\mathcal{R}\mathcal{E}$

Notations

• $ϵ$ - empty string representing empty set $\varnothing$ or $\{ϵ\}$
• any symbol '$a$' from the input alphabet representing $\{a\}$
• Union $(a+b)$ representing $\{a,b\}$
• Concatenation $(ab)$ which is valid if and only if $a,b$
• Kleene Star $(a{)}^{\ast }$ zero or more occurrences of $a$

Alphabet Definition

The alphabet includes: $\mathcal{R}\mathcal{E}=\{\varnothing ,ϵ,+,\ast ,(,)\}$. Assumes the alphabet you match does not include any of these symbols.

Definition

Define the set of regexes of $\Sigma$ Let $\mathcal{R}\mathcal{E}$ be the smallest set such that: Basis: $\varnothing ,ϵ\in \mathcal{R}\mathcal{E},c\in \mathcal{R}\mathcal{E},\forall c\in \Sigma$

• Note that $\varnothing$ is a symbol, not the set
• Note that $ϵ$ is a symbol, not the string Induction step: if $S,T\in \mathcal{R}\mathcal{E}$, then $(S+T),(ST),S^{\ast }\in \mathcal{R}\mathcal{E}$

Concepts

• Regex Matches
• Regex Precedences

Properties

• Commutivity of union ( $(R+S)=(S+R)$)
• Associative of union ($((R+S)+T)=(R+(S+T))$)
• Associative of concatenation ($(((RS)T)=(R(ST)))$)
• Left Distributive ( $R(S+T)=((RS)+(RT))$ )
• Right Distributive ( $(S+T)R=((SR)+(TR))$)
• Identity for union $(R+\varnothing )\equiv R$
• Identity for concatenation $(Rϵ)=(ϵR)=R$
• Annihilator for concatenation $(\varnothing R)=(R\varnothing )=\varnothing$
• Idempotence of Kleene Star $R^{\ast \ast }\equiv R^{\ast }$
• ${ϵ}^{\ast }=ϵ$
• ${\varnothing }^{\ast }=ϵ$
• $R^{\ast }{R}^{\ast }=R^{\ast }$
• $R{R}^{\ast }=R^{\ast }R$
• $ϵ+R{R}^{\ast }=ϵ+R^{\ast }R=R^{\ast }$
• $(PQ{)}^{\ast }P=P(QP{)}^{\ast }$
• $(P+Q{)}^{\ast }=(P^{\ast }{Q}^{\ast }{)}^{\ast }=(P^{\ast }+Q^{\ast }{)}^{\ast }$

Identities