A regular expression expresses a language that can be modelled by a NFA. This article lists the procedure to follow to convert a regular expression to an equivalent NFA. A regular expression can be one of the following cases.

This expression means the empty set. No string is in the language of this expression. An equivalent NFA will be

This expression means the empty string. The difference between the empty string and the empty set is discussed in detail here. An equivalent NFA which accepts the empty string, will be

This expression means a single symbol in the alphabet . An equivalent NFA which accepts the string, will be

This expression is the union of two regular expressions. The NFAs for and are shown in two different colors. An equivalent NFA which accepts the union of the two expressions is given below.

This expression is the concatenation of two regular expressions. The NFAs for and are shown in two different colors. An equivalent NFA which accepts the concatenation of the two expressions is given below.

This expression is the Kleene star of a regular expression. The NFA for is shown in color. An equivalent NFA which accepts the Kleene star of this expression is given below

Example

Here is an example showing how to build an NFA for the following complex expression.

The changes in the NFA for each expression are indicated with a color.

This can be simplified to

This can be simplified to

Concatenating the two simplifications, the final NFA is given below

---

References

• https://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec35-kleene.html