4.3. The Power of Regular Expressions¶

Now that we know the definition for Regular Expressions and have a bit of experience with writing them, the next order of business is understanding how powerful they are. In particular, a natural question to ask is: What is the relationship between Regular Expressions and Regular Languages? Recall that a Regular Language is defined to be any langauge that can be accepted by a DFA (and equivalently, any language that can be accepted by a NFA).

In this section, we will use our standard approach of simulation to show that Regular Expressions are equivalent to Regular Languages. By this, we mean that a Regular Expression can be converted to a representation for a Regular Language (in particular, a NFA). Therefore, any Regular Expression represents a Regular Language. Going the other way, any Regular Language (in the form of an NFA) can be converted to a Regular Expression. Thus, any Regular Language can be represented by a Reglar Language. The conclusion is then that these are equivalent.

4.3.1. Every Regular Expression has an Equivalent NFA¶

1 / 13 Settings

<<<>>>

Part 1. Recall that we define the term regular language to mean the languages that are recognized by a DFA. And we know these are the same as the languages recognized by an NFA, because we know that every NFA can be converted to a DFA (and vice versa).

Now, we will show the relationship between regular languages (and thus, DFAs and NFAs) and Regular Expressions.

s

f

λ

λ

λ

Saving...
Server Error
Resubmit

Summary: We have now shown that (1) an RE consisting of $\lambda$ or of a single symbol from the alphabet can be represented by an NFA, and (2) we can convert any NFA to an equivalent NFA with a single final state. This simplifies the rest of the constructions that we will use.

1 / 12 Settings

<<<>>>

Part 2. In Part 1, we showed how to convert the base case REs ($\lambda$ and any symbol from $\Sigma$) to NFAs. And we showed that any NFA can be converted to an equivalent NFA with a single final state.

Now we will see how to convert more complex REs to an NFA.

s

f

λ

λ

λ

NFA that accepts $r$

s

f

λ

λ

λ

NFA that accepts $s$

s

λ

λ

f

λ

λ

Saving...
Server Error
Resubmit

1 / 12 Settings

<<<>>>

Part 3. Next, we will define a construction for the NFA that can accept the RE $r \cdot s$, given that we have NFAs that are equivalent to $r$ and $s$.

s

f

λ

λ

λ

NFA that accepts $r$

s

f

λ

λ

λ

NFA that accepts $s$

s

λ

λ

f

λ

Saving...
Server Error
Resubmit

1 / 12 Settings

<<<>>>

Part 4. The last operator that we need to implement is the Kleene star ($*$) operator. The operator will concatenate the language with itself zero or more times.

s

f

λ

λ

λ

NFA that accepts $r$

s

λ

f

λ

λ

λ

Saving...
Server Error
Resubmit

Now let’s spell out the entire induction proof.

Theorem 4.3.1

Theorem: Any RE can be converted to an equivalent NFA.

Proof: We will prove this using induction.

1. Base Case: REs $\lambda$ and symbols $a \in \Sigma$ can be all be converted to NFAs as demonstrated by the constructions in Part 1 above.

2. Induction Hypothesis: When trying to build the NFA equivalent to $t$ that was created using one of the construction rules $t = r + s$, $t = rs$, or $t = r^*$, we can assume that $r$ and $s$ can be converted to NFAs.

3. Induction Step: By definition, any RE $t$ must either be a member of the base case or built by one of the three builder rules. If it can be formed using one of the builder rules, then from the induction hypothesis we can assume that $r$ and $s$ used to build $t$ can be converted to equivalent NFAs. From the constructions shown in Parts 1, 2, 3, and 4 above, $t$ can therefore also be converted to an equivalent NFA.

Summary: Using an inductive argument, we have now demonstrated that we can convert any RE to an NFA. So, all REs accept a regular language.

4.3.2. Converting a Regular Expression to a NFA¶

1 / 20 Settings

<<<>>>

We now have a proof that any RegEx can be converted to a NFA. And we know some mechanics: In particular, we know how to combine two NFAs that represent RegExs into a single NFA using one of the RegEx builder rules. Unfortunately, that does not really help us when faced with a complex RegEx that we want to convert to an NFA. In this frameset, we show an algorithm for doing this.

q0

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

$\lambda$

$\lambda$

c

$\lambda$

$\lambda$

a

$\lambda$

$\lambda$

$\lambda$

$\lambda$

$\lambda$

$\lambda$

b

$\lambda$

q0

q1

$ab^* + c$

q2

q3

q4

q5

q6

$\lambda$

$\lambda$

$ab^*$

c

$\lambda$

$\lambda$

q6

q7

q8

q9

$\lambda$

a

$\lambda$

$b^*$

$\lambda$

q10

q11

$\lambda$

b

$\lambda$

$\lambda$

$\lambda$

Saving...
Server Error
Resubmit

4.3.3. Regular Expression to Minimized DFA Example¶

1 / 30 Settings

<<<>>>

In this example, we will convert the regular expression ab*+c to a minimized DFA.

q0

q1

ab*+c

q2

q3

ab*

q4

q5

c

λ

λ

λ

λ

q6

q7

a

q8

q9

b*

λ

λ

λ

q10

q11

b

λ

λ

λ

λ

q0,q2,q4,q6

q1,q5

c

q1,q10,q3,q7,q8,q9

a

q1,q10,q11,q3,q8,q9

b

b

q4

c
a
b

b

c

c

c

q0,q4

q1,q2,q3

q4

c

q0

c

q1

b

q2,q3

b

q4

q0

q1

q2,q3

c

a

b

c
a
b

b

c
a

c
a
b

Saving...
Server Error
Resubmit

4.3.4. Converting NFAs to Regular Expressions¶

1 / 32 Settings

<<<>>>

Since every regular expression has an NFA that implements it, this means that the regular expressions are a subset of the regular languages. The next question is: Does every regular language have a regular expression?

Perhaps you thought it fairly intuitive to see that any regular expression can be implemented as a NFA. But for most of us, going the other way is not at all obvious. The proof that any NFA can be converted to a regular expression is rather difficult, and we are just going to give a sketch.

Saving...
Server Error
Resubmit