From Regular Expression to Nondeterministic Finite Automaton | Theory of Computation
Channel: David Spry
Date: 2022-08-13

This video outlines a simple method for converting from a regular expression to an equivalent nondeterministic finite automaton (NFA).

- - - - - - - - - - - - - - - - - - - - -
0:00 Introduction
"Hello. I'm going to describe a method for building a nondeterministic finite automaton -- a NFA -- from a regular expression."

0:13 Generalised NFA
"Here's an example of a generalised NFA that recognises the regular language described by R, which is some arbitrary regular expression. If we read a word that belongs to this language, then we can move from the start state on the left, along the single transition labelled by R, and arrive at the Accept state on the right. This is true for any regular expression, so constructing a generalised NFA from a regular expression is as simple as defining R. 

However, as our goal is to construct an NFA -- not a generalised NFA -- I'm going to describe a method for breaking R into a composition of smaller, atomic regular expressions and representing each of those smaller regular expressions by a particular pattern of states and transitions."

1:05 Patterns
"Here are the patterns that we'll need. 

[0. Character] If R is simply a character, such as the character 'a', then R will be represented by two states with a transition between them to represent the character.

[1. Concatenation] If R is the concatenation of two regular expressions, A and B, then R will be represented by three states. A transition from state 1 to state 2 will represent A, and a transition from state 2 to state 3 will represent B.

[2. Union] If R is either A or B, as in the union operation, then R will be represented by two states with a transition between them for A and transition between them for B.

[3. Kleene Star] If R is some expression, A, followed by a Kleene star, then R will be represented by three states, with empty transitions coming into and coming out of the second state, and a loop on the second state to allow A to be repeated zero or more times.

Building a NFA from a regular expression is a matter of repeatedly applying these patterns, recursively, to R."

2:18 Example #1
"Here's an example. Let's use the regular expression R = (aa U bb) a*. To begin the construction of the NFA, create a start state and an accept state and label a transition between them with R.

R is a concatenation of two expressions -- (aa U bb) and a* -- so we can replace the 'R' transition in the NFA with the concatenation pattern.

The left-hand side of the concatenation is a union of two expressions -- aa, and bb -- so we can replace its transition in the NFA with the union pattern.

Incidentally, both of the operands of the union operation are concatenations of two characters, so their transitions can be replaced with the concatenation pattern.

As you can see, only one reducible regular expression remains: a*. Let's replace its transition in the NFA with the Kleene star pattern, symbolising the empty transitions with the epsilon character.

Now that we've fully reduced R, we have finished the construction of the NFA. This NFA is equivalent to R, which is to say that the language that this NFA recognises is the language described by R."

3:41 Example #2
"Let's look at another example. This time, we'll set R equal to (ab U ba)*. As before, begin the construction of the NFA with a start state and an accept state, and label a transition between them with R.

R is an expression -- (ab U ba) -- followed by a Kleene star, so replace the 'R' transition in the NFA with the Kleene star pattern, representing empty transitions with the epsilon symbol.

The expression on the loop transition is a union operation of two expressions -- ab and ba -- so we can replace the loop transition, which is a transition from a state to itself, with the union pattern. In this case, the existing loop is replaced by two loops.

Finally, we'll replace both of these new loops -- whose expressions are both concatenations of two characters -- using the concatenation pattern."

4:44 Exercises
"Here are three regular expressions for you to construct NFAs from. I'll add NFAs for each of these to the end of the video so that you can compare your results with mine."

4:55 Ending
"Thanks for watching this video. I hope that it was helpful for you. If you have any questions or requests for more videos like this one, then please let me know. Goodbye."

5:07 Solutions