Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
