# How to formally prove that any regular expression can be written as a finite combination of base cases and operations?

In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows:

Based on this definition, how can I formally prove that any regular expression can be written as a finite formula where each of the elements in the formula are either:

1. Parentheses,
2. Union operation, concatenation operation, or Kleene star operation,
3. One of the basic regular languages, i.e., a letter from the alphabet, the empty string, or the empty language.
• (May be difficult: I see no requirement of finiteness in Definition 1.52.) Commented Jun 11 at 10:53

## 1 Answer

What you have there is a recursive definition. Every regular expression is generated by a finite number of applications of rules 1.-6., so you can simply do mathematical induction over the number of steps required to derive your expression¹.

So start like this:

• If $$R$$ was derived in 1 step, then it must have the form $$R = a \in \Sigma$$, $$R = \varepsilon$$ or $$R = \emptyset$$. Therefore...
• Assume that all regular expressions derived in $$\leq n$$ steps have the desired property.
• If $$R$$ was derived in $$n + 1$$ steps, then $$R$$ must have the form $$R = (R_1 \cup R_2), R = (R_1 \circ R_2)$$ or $$R = R_1^*$$ where $$R_1, R_2$$ were derived in $$\leq n$$ steps. Using the induction hypothesis...

#### Why is every regular expression generated in a finite number of steps?

The recursive definition as written is a bit ambiguous. It only tells us which objects are regular expressions, but not which objects aren't. It is (sadly) often left implied, but when speaking about a recursively defined set, we usually mean the smallest set satisfying the requirements.

So given the definition above, we would formally define the set of regular expressions as the smallest set $$\mathcal{R}$$ satisfying 1. and 2. below

1. $$a, \varepsilon, \emptyset \in \mathcal{R}$$ for all $$a \in \Sigma$$
2. $$(R_1 \cup R_2), (R_1 \circ R_2), (R_1^*) \in \mathcal{R}$$ if $$R_1, R_2 \in \mathcal{R}$$

Now define the function $$S: \mathbb{N} \to \wp(\mathcal{R})$$ (by the recursion theorem) as follows

• $$S(0) = \{\varepsilon, \emptyset\} \cup \Sigma$$
• $$S(n + 1) = \{(R_1 \cup R_2), (R_1 \circ R_2), (R_1^*), R_1 : R_1, R_2 \in S(n)\}$$

Intuitively, think about $$S(n)$$ as the set of regular expressions derivable in $$n$$ steps or less. Define $$\mathcal{R}' := \bigcup_{n \in \mathbb{N}} S(n)$$

and note, that $$\mathcal{R}' \subseteq \mathcal{R}$$. Since $$\mathcal{R}'$$ also satisfies 1. and 2. above, it follows that $$\mathcal{R} \subseteq \mathcal{R}'$$ since $$\mathcal{R}$$ is the smallest set satisfying 1. and 2.

So $$\mathcal{R} = \mathcal{R}'$$.

1 You can also use structural induction, you might have already encountered it in a similar context in a formal logic class.

• Thank you for your response. I have a follow-up question regarding your assumption that every regular expression is composed of a finite number of steps. You mentioned that each regular expression is generated by a finite number of applications of the rules (1-6). Could you please clarify or formally justify this assumption? Specifically, how does the recursive definition ensure that the construction process will always terminate after a finite number of steps? I'm looking for a rigorous explanation or proof based solely on the definition provided. Commented Jun 14 at 22:38
• @Vegetal605 Sorry, I totally forgot about this 😅 I'll add an addition to my answer later today/tomorrow. Commented Jun 19 at 10:34
• Thanks so much for the detailed explanation and the addition about the recursion theorem. Your clarification really helped me understand why every regular expression is generated in a finite number of steps. Commented Jun 23 at 7:39