# Confused by Sipser's proof of equivalence of R and NFAs

I am reading Introduction To Theory of Computation by Sipser, 3rd Edition and am confused by his take on the last three cases of proving that "if a language is described by regular expression then it is regular" on Page 67.

I don't understand how this proof guarantees that there will be an NFA for R1 and R2 in the first place. I understand that if there were NFAs for them then I could construct an NFA for their union/concatenation/star.

Let's consider $$R_1$$ only but the idea applies to $$R_2$$ as well. It should be clear that $$R_1$$ is a regular expression. Thus, it must be one of the six cases. If it's the first 3, then you are done - construct the NFA for $$R_1$$ using one of the 3 cases. Otherwise, you can decompose $$R_1$$ into smaller regular expression satisfying one of the remaining 3 cases, e.g. $$R_1 = R_3 \cup R_4$$. Recursively apply the construction to the smaller expressions of $$R_1$$. When you have recursivley constructed the smaller NFA for the components of $$R_1$$, apply the union/concatenation/star (depending on what kind of exression $$R_1$$ is) construction of NFA to create $$R_1$$.