Regular Expression

Symbolic notations used to define search patterns of strings.

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$
• Klene Expression $(a{)}^{\ast }$ zero or more occurances of $a$