---
Video Title: Equivalence of Regular Expressions and Finite State Automata
Description: Theory of Computation
https://uvatoc.github.io/week7

14.2: Equivalence of Regular Expressions and Finite State Automata
- How to prove two computing models are equivalent
- Strategy for proving regular expressions are equivalent to FSAs

(Proof that regular expression can be converted to FSA is in next segment.)

Nathan Brunelle and David Evans
University of Virginia
---

What we're going to be doing is we're
going to be making progress towards this

demonstration that finite
state automata and regular

expressions are equivalent
models of computing.

Any language that I could represent with a
regular expression, I could also represent

with a finite state automaton and vice
versa.

We're going to be making more progress
towards that, but we're not quite going to

have all of the mechanics that we need
just yet.

We're going to get close.

Today, we're going to be talking about two
main topics.

The first topic we're
going to be talking about

is we're going to talk
more about closure.

That is, we're going to show what sort of
operations can we do to languages,

such that if we started with a language
computable with a finite state automaton,

we'd end with a language computable with a
finite state automaton.

And then we're also going to be talking
about this idea of non-determinism.

You can kind of think
about this as a superpower

that we could give to
models of computing.

Basically, we're just like, we're not going
to care about what physics says anymore.

We're just going to do whatever.

And the idea of this non-determinism
is a more relaxed model

of what machines can do,
what finite state automata can do.

And in particular, it allows us to do
several things at once.

This idea of non-determinism just means
we're able to do several things at once.

This is useful for kind of modeling
parallel computing.

And also for modeling quantum computing.

Parallel computing and
quantum computing both

behave in kind of
non-deterministic ways.

We often think about them like that
anyway.

But the idea of non-determinism we're
going to see is that we're going to say

that instead of your computer
just doing one thing at a time,

it's able to do many, many,
many, many things at a time.

We're going to define that a little bit
more precisely later in class today.

So last class, we talked about regular
expressions, where a regular expression

was some way of describing
a language by basically

giving a pattern for all of
the strings in that language.

So any string that matched to the pattern,
we said belong to the language,

strings that didn't match the pattern,
they didn't belong to the language.

So in that sense, that's how regular
expressions are kind of a model of

computing, because they tell us which
things are and are not in some language.

And we know that there is kind of this
relationship between functions and languages.

Our regular expression
had several different pieces

for things we could include
in our regular expressions.

We had the empty string,

so we were allowed to talk directly about
the empty string using either double

quotes or this epsilon character that
looks like a backwards three.

We could use literal characters,
so that is things from our alphabet.

So characters from our alphabet could be
included in our regular expressions.

We could have alternation or union.

So that is this vertical bar which says
the first thing or the second thing.

So it can match either the first regular
expression or the second regular expression.

We add concatenation, which says that the
string needed to be composed of two pieces

where Where the first piece matched the
first regular expression.

The second piece matched the second
regular expression.

And then we add this Kleene star where we
said you can take zero or more copies of

some regular expression
for a string to match

a regular expression
with a Kleene star.

We need to be able to break it up into as
many pieces as we would like where every

single one of those pieces matches that
regular expression inside the star.

So our ultimate goal right now is to
demonstrate this proof that as a model of

computing, finite state automata are
equivalent to regular expressions.

So we've shown proofs like this before.

We've shown proofs of this
format where I've got two models

of computing and I want to
show that they're equivalent.

So, for instance, we said that if we had
AND or NOT circuits compared with NAND

circuits, we showed that those were
equivalent models of computing.

How did we show that?

Yeah.

Yeah, so basically we showed that we could
take anything that we could do in one

model of computing and we could sort of
translate it into this other model,

such that the functions that we computed
were going to be the same in the

pre-translated version and the
post-translated version.

Basically, we show this by providing some
sort of mechanism for translating,

for translating model A into model B.

So that's what we're going to be doing in
order to show that finite state automata,

as a model of computing, are equivalent to
regular expressions.

They have equal power to regular
expressions.

So, we can show that any
finite state automata can be

translated into some regular
expression for the same language.

And any regular expression
can be converted into

some finite state automata
for the same language.

If I did that, then we
could conclude finite state

automata are equivalent
to regular expressions.

So, if I wanted to show that regular
expressions were at least as powerful as

finite state automata, so kind of the
power of a regular expression is greater

than or equal to finite state automata,
then that means that I need to be able to

show that I can take
any finite state automaton

and translate it into
a regular expression.

If I could take any finite state automaton
and translate it into a regular

expression, then that
means anything an

automaton could do a
regular expression could do.

So regular expressions must be at least as
powerful.

If I could translate a finite state
automaton into a regular expression that

says anything a finite state automaton can
do, a regular expression could do as well.

So regular expressions are at least as
powerful.

We're not going to do this in class.

I'm not going to ever expect
you to implement something

like this or be able to do
this by hand or whatever.

That's because it's tedious, it requires a
lot of legwork to get there, and it's not

actually super useful in application to go
in that direction.

It's very, very rare that in application
anybody ever goes in that direction.

So I'm just going to skip it, but I'm
going to tell you that Textbook Theorem

9.12 demonstrates that for you if you care
to see it nonetheless.