Regular Expressions $\mathrm{RegEx}$

Regular expressions describe languages based on algebra operations. The language defined by regular expression $w$ is $L(w)$, which is exactly regular language.

Regular Expression Definition (Bases)

A regular expression is defined as follows:

• Basis1: If $a$ is a symbol in the alphabet, then $\mathbf{a}$ is a regular expression and $L(\mathbf{a})$ represents the language $\{a\}$.
• Basis2: $ϵ$ is a regular expression and $L(ϵ)$ represents the language $\{ϵ\}$.
• Basis3: $\mathrm{\varnothing }$ is a regular expression and $L(\mathrm{\varnothing })$ represents the language $\mathrm{\varnothing }$.

Regular Expression Operators (Inductions)

The regular expression operators are defined as follows:

• Induction 1 (Union): If $R_1$ and $R_2$ are regular expressions, then $R_1+R_2$ is also a regular expression. $R_1+R_2$ is the set of strings that are in $R_1$ or $R_2$.
• Induction 2 (Concatenation): If R1 and R2 are regular expressions, then $R_1\cdot R_2$ is also a regular expression. $R_1\cdot R_2$ is the set of strings that are the concatenation of a string in $R_1$ followed by a string in $R_2$.
• Induction 3 (Kleene Star): If $R$ is a regular expression, then $R^{\ast }$ is also a regular expression. $R^{\ast }$ is the set of strings that are the concatenation of zero or more strings in $R$.

Precedence of Operators

The precedence of operators is as follows:

• Kleene Star has the highest precedence.
• Concatenation has the second highest precedence. The concatenation operator is implicit, so it is not necessary to write it.
• Union has the lowest precedence.

Regular Expression Examples

• Example 1: $L((0+1{)}^{\ast })$ represents the set of all binary strings.
• Example 2: $L((0+10{)}^{\ast }(1+\epsilon ))$ represents the set of all binary strings that have no two consecutive $1$s.

Equivalence of Regular Expressions and Finite Automata

Regular expressions and finite automata are equivalent. A regular expression can be easily converted to a NFA by using Thompson's construction method. For any regular expression $R$, there exists an NFA $N(R)$ such that $L(R)=L(N(R))$. We can construct the corresponding NFA by following these rules:

• Basic Rules

  • If the regular expression is a symbol $a$, then it is converted to an NFA with two states.
  

  R is only a symbol 'a'

  • If the regular expression $R$ is $\epsilon$, then it is converted to an NFA with two state, linked by an $ϵ$-transition.
  

  R is epsilon

  • If the regular expression is $\mathrm{\varnothing }$, then it is converted to an NFA with two states, but without any transitions.

• Inductive Rules

  • If the regular expression is $s+t$, then the NFA is like a choice between the NFAs for $s$ and $t$.
  

  R is s + t

  • If the regular expression is $s\cdot t$, then the NFA sequentially combines the NFAs for $s$ and $t$.
  

  R is s.t

  • If the regular expression is $s^{\ast }$, then the NFA for $s^{\ast }$ is a loop that can be taken zero or more times.
  

  R is s*

DFA to $\mathrm{RegEx}$

First, we need to define the concept of $k-$paths. $k-$paths is a path through the graph of the DFA that goes through $k$ intermediate states. It is easy to show that $n-$paths (The number of states in the DFA is $n$) are unrestricted.

The idea of the algorithm is to find the corresponding regular expression for the $k-$paths for $k=0,1,\cdots ,n$. The regular expression for the $n-$paths is exactly the regular expression for the language of the DFA.

Let $R_{ij}^{(k)}$ be the regular expression for the $k-$paths from state $i$ to state $j$. The algorithm is as follows:

• Basis: For $k=0$, $R_{ij}^{(0)}$ is the sum of symbols of the arc that directly connect state $i$ to state $j$. If there is no arc, then $R_{ij}^{(0)}=\mathrm{\varnothing }$. But if $i=j$, then add $\epsilon$.
• Induction: For $k=1,2,\cdots ,n$, the regular expression $R_{ij}^{(k)}$ is the sum of the regular expressions $R_{ij}^{(k-1)}+R_{ik}^{(k-1)}(R_{kk}^{(k-1)}{)}^{\ast }{R}_{kj}^{(k-1)}$. We can comprehend this formula as follows:
  • The $k-$paths from $i$ to $j$ can be divided into two parts: the $k-$paths that do not go through state $k$ and the $k-$paths that go through state $k$.
  • The $k-$paths that do not go through state $k$ are the same as the $k-$paths from $i$ to $j$, i.e., $R_{ij}^{(k-1)}$.
  • The $k-$paths that go through state $k$ must visit state $k$ at least once. Thus, the regular expression for these paths is $R_{ik}^{(k-1)}(R_{kk}^{(k-1)}{)}^{\ast }{R}_{kj}^{(k-1)}$. The middle term $(R_{kk}^{(k-1)}{)}^{\ast }$ allows the path to loop in state $k$.

Finally, the regular expression for the language of the DFA is $R_{st}^{(n)}$, where $s$ is the start state and $t$ is the final state, $n$ is the number of states in the DFA.

Summary

Each of the three types of automata (DFA, NFA, $\epsilon -$NFA) we discussed, along with $\mathrm{RegEx}$, define exactly the same class of languages, which is the class of regular languages. What is really interesting is that for a long time in the history of computer science, people believed that regular expressions were more powerful than DFAs. However, it was later proven that they are equivalent in power, which makes it a great example of how the study of automata theory can help us understand the limits of computation.