4.1.1. Definition and Examples of Regular Expressions¶

1 / 27 Settings

<<<>>>

This slideshow presents the definition and some examples for Regular Expressions.

Saving...
Server Error
Resubmit

Definition for Regular Expressions (RE): Given $\Sigma$,

1. $\lambda$, and all $a \in \Sigma$ are RE

2. If $r$ and $s$ are regular expressions, then

   • $r + s$ is a RE

   • $r s$ is a RE

   • $(r)$ is a RE

   • $r^*$ is a RE

3. $r$ is a RE if and only if it can be derived from (1) with a finite number of applications of (2).

4.1.2. Converting a Regular Expression to a 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 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

Summary: We can convert any RE to an NFA. So, all REs accept a regular language.

4.1.3. Regular Expression to NFA Conversion Example¶

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.1.4. 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.1.5. Converting Regular Languages 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

4.1.6. Converting Regular Languages to Regular Expressions Example¶

0 / 0 Settings

<<<>>>

After removing all nodes that are not final and not start, the resulting Regular Exepression is:

Saving...
Server Error
Resubmit

4.1.7. Summary¶

We have now demonstrated several things:

• Any RegEx can be represented by an NFA or a DFA.

• Any NFA (or DFA) can be represented by a RegEx.

Thus, all languages that can be represented by regular expression are regular, and all regular languages can be represented by a regular expression.

As we noted at the start, regular expressions don’t give us any more power than we already had with DFAs. But they are often easier to write down, as you will see in the following exercises.