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.

enter image description here enter image description here


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.