Regular Expressions

REs $R$ and $S$ are equivalent if they denote the same language, written $R$ = $S$.

• Example: (a | b)* = (a*b*)*

Figure 3.7: Algebraic Laws for REs

• $R$ | $S$ = $S$ | $R$ (| commutative)
• $R$ | ($S$ | $T$) = ($R$ | $S$) | T (| associative)
• $R$ ($S$ $T$) = ($R$ $S$) $T$ ($\cdot$ associative)
• $R$ ($S$ | $T$) = $R$ $S$ | $R$ $T$ ($\cdot$ distributes over |)
• $\varepsilon$ $R$ = $R$ $\varepsilon$ = $R$ ($\varepsilon$ is $\cdot$ identity)
  

RE Notation

Figure 3.8: Lex regular expressions