Regular Expressions

Section: Finite Automata = Regular Languages

Regular expressions have three operators:

$$\begin{array}{rl}+& \text{Union}\\ \ast & \text{Zero or More}\\ \circ & \text{Concat}\end{array}$$

1. Begin with $\varphi ,\lambda ,\Sigma \in \text{RegEx}$
2. All above operators on the three, and the alphabet, is a regular expression

Example

→ Odd number of a’s, and then even number of b’s: $a(aa{)}^{\ast }(bb{)}^{\ast }$ → 3 or less a’s and ends in ab: $b^{\ast }(a+\lambda )b^{\ast }(a+\lambda )b^{\ast }ab$

RegEx $\equiv$ DFA §

pf. RegEx ⇒ DFA

1. First define the building blocks

Representation of $\varphi$

Representation of $\{a\}$

Representation of $\lambda$

1. Then buid on them recursively:

pf. DFA ⇒ RegEx

1. With a DFA with one final state, convert into a generalized transition graph (GTG) [=edges can be a RegEx]
2. If the GTG has two states: Unique RegEx for this DFA: $(r_{ii}^{\ast }{r}_{ij}{r}_{jj}^{\ast }{r}_{ji}{)}^{\ast }{r}_{ii}^{\ast }{r}_{ij}{r}_{jj}^{\ast }$
3. If GTG has three or more states it is in the form: