---
Video Title: Proving FSAs are as Powerful as Regular Expressions
Description: Theory of Computation
https://uvatoc.github.io/week7

14.3: Proving FSAs are as Powerful as Regular Expressions
Part 1: Proof Strategy

Nathan Brunelle and David Evans
University of Virginia
---

This is the one that we care about,
is to show that finite state automata are

at least as powerful as regular
expressions.

And the way we're going to do this is
we're going to show that I can take any

regular expression and I can convert that
into an equivalent finite state automaton.

So we're going to show the translation in
this direction.

So to show that finite state automata are
at least as powerful as regular

expressions, I'm going to give a general
way of taking any regular expression and

converting it into an equivalent finite
state automaton.

And the strategy we're going to use to do
this is we're going to show that every

piece that we had identified a regular
expression as being allowed to have,

we could build automata that did the same
thing as those pieces.

So the idea here is with all of these
pieces of a regular expression,

empty string, literal character,
and so forth, I'm going to show that I can

take the regular expression
of the empty string

and I can make a finite
state automaton for that.

And then I'm going to show
that I can take any literal

character and I can make a
finite state automaton for that.

And then I'm going to show
that if I had two finite state

automata, I could combine
them with union or alternation.

So if I had two languages that I could
represent or compute with a finite state

automaton, then I can also
find a finite state automaton

that can compute the union
of those two languages.

So we're kind of mimicking this operation
that we can have inside regular

expressions by doing the parallel
operation on finite state automata as well.

So I can build regular
expressions by saying empty

strings or literal characters
combined with alternation.

I'm going to show that I can take finite
state automata for the empty string,

finite state automata for literal characters,
and combine those with alternation.

And then I'm going to do the same thing
for concatenation.

I'm going to show that if I have two
finite state automata, each computing some

language, I can find a third
finite state automaton that

can compute the concatenation
of those two languages.

So if I had things that had regular
expressions, and I could convert those two

things into finite state automata,
then I can take those two finite state

automata and do a concatenation
on them in order to do

the same thing as
concatenating regular expressions.

And same with clany star.

If I have a finite state automaton for
some language, I can create a finite state

automaton for the clany star of that
language, for that operation on the language.

So this proof technique
that we're using here, this

is actually a special
kind of proof by induction.

The way that our regular
expressions are defined is to say that

we have base cases like
empty string and literal character.

So those are going to be base cases.

Those are kind of the simplest regular
expressions I could have.

Just having a literal character or having
the empty string or something like that.

And then we have rules for how I can build
more and more and more complicated regular

expressions from those
simple pieces, which is

by combining them together
with these operations.

So what we've described here
with these pieces of a regular

expression is rules for
building regular expressions.

Every regular expression is going to be an
empty string, or it's going to be a

literal character, or it's going to be an
alternation of two regular expressions,

or it's going to be a concatenation
of two regular expressions,

or it's going to be a cleanly
star of a regular expression.

And I can just build those
up arbitrarily to make more

and more and more
complicated regular expressions.

So we have rules for building regular
expressions.

And we're going to show that we can start
with simple finite state automata.

And build up finite state
automata to be more and more

complicated such that we can
build them up using these same rules.

So if I show these base
cases where I can have

a finite state automaton
for an empty string.

And I can have a finite state automaton
for a literal character.

And I can show that if I take any two
finite state automata and can combine them

together using these rules that regular
expressions have for combining.

Then I should be able
to build a finite state

automaton to match
any regular expression.

So this is our strategy.

This is the strategy we're going to use in
order to prove this.

So in order to finally demonstrate this,
in order to actually arrive at our

conclusion, we just have
to show that I can build

finite state automata for
each one of these pieces.